숫자 자바에서 배열을 추가하여 얻을 수 있습니다

Question

배열의 다른 번호를 추가하여 얻을 수없는 최소 숫자를 가져와야합니다. 기본적으로 내가이 숫자를 가지고 있다면 : 1,1,1,5; 나는 1,2,3,5,6을 얻을 수있다. 그러나 나는 4를 얻는다. 그래서 그것은 내가 찾고있는 수다. 지금 이것은 내 코드입니다 :

import java.util.Scanner; 
public class Broj_6 { 

public static void main(String[] args) { 
    Scanner unos = new Scanner(System.in); 
    int k; 
    int n = unos.nextInt(); 
    int niz []= new int [n]; 
    for(int i = 0;i<n;i++){ 
     niz[i]=unos.nextInt(); 
    } 
    BubbleSort(niz); 
    for(int i = 0;i<n;i++){ 
     System.out.print(niz[i] + " "); 
    } 
    for(int br = 1;br<=10000;br++){ 
     for(k = 1;k<n;k++){ 
      if(niz[k]>br){ 
       break; 
      } 
     } 
     int podniz [] = new int [k]; 
     for(int i=0;i<podniz.length;i++){ 
      niz[i] = podniz[i]; 
     } 
     //This is where I will need my logic to go 
    } 
} 

static void BubbleSort (int [] niz){ 
    int pom; 
    for(int i = 0;i<niz.length-1;i++){ 
     for(int j = 0;j<niz.length-1-i;j++){ 
      if(niz[j]>niz[j+1]){ 
       pom = niz[j]; 
       niz[j] = niz[j+1]; 
       niz[j+1] = pom; 
      } 
     } 
    } 
} 
} 

그래서 코드는 100000에 1부터 개별적으로 각 수를 테스트하여 이동 및 숫자 자체보다 작은 주어진 모든 숫자의 부분 배열한다. 이제 여기에 문제가 있습니다. 나는 원하는 번호를 얻거나 얻을 수 있도록 하위 배열의 숫자를 혼합하고 일치시키는 법을 모릅니다. 모든 조합이 테스트되고 원하는 숫자가 없을 때 나는 깨뜨릴 것이다. 루프와 인쇄. 그냥 난 단지 또한 사용할 수 있습니다 명확히하고, 각 숫자는 단지 당신은 다음과 같이이를 달성 할 수

Answer 1

한 번에 갈 수 있습니다 :

List<Integer> additionList = new ArrayList<Integer>(); 
int []inputNumbers = .... // Logic to read inputs 
for(int _firstIndex = 0; _firstIndex < totalInputs; _firstIndex++){ 
    for(int _secondIndex = _firstIndex + 1; _secondIndex < totalInputs; _secondIndex++){ 
     additionList.add(inputNumbers[_firstIndex]); // only because you have 1 in the sample output 
     additionList.add(inputNumbers[_firstIndex] + inputNumbers[_secondIndex ]); 
    } 
} 

: 다른 번호의 합을 계산하기 위해 다음과 같은 두 개의 중첩 루프를 사용

그런 다음 additionList을 정렬하고 누락 된 항목을 찾으십시오. 첫 번째 누락 된 항목은 대답이 될 것입니다.

Answer 2

전체 배열을 정렬 한 다음 모든 하위 배열의 합계를 찾는 것이 문제를 해결하지만 값이 비쌉니다 : O (2n^2) ~ O (n^2).

http://en.wikipedia.org/wiki/Maximum_subarray_problem가 너 한테이 무엇 : 첫 번째 요소에서 시작하고 당신이 원하는하고 합에 도달 할 때까지 배열의 크기 (하위 배열)를 증가 이 문제를 해결하기 위해

더 효율적인 방법은 Kadane의 알고리즘이 될 것입니다.

my_num = 1; 
while(true){ 
    if(sum_subarray) > my_num){ 
    current position = new subarray; 
} 

이 부분 배열의 개념은 Kadane의 접근 방식을 통해 계산된다

def sum_subarray(A): 
sum_ending_here = sum_so_far = 0 
for x in A: 
    sum_ending_here = max(0, max_ending_here + x) 
    sum_so_far = max(sum_so_far, sum_ending_here) 
return sum_so_far 

내가 문제를 완전히 해결할 수 있습니다. 여기서 언급 한 'my_num'은 1에서 증가해야하고 my_num > max_sum 일 때 중단되어야합니다. 누군가가 그것에 추가하여 컴파일 할 수 있기를 바랍니다.

참고 : 음성 요소 어레이에 존재하는 경우가

이것도 조심한다.