n 개의 숫자가 원으로 배열됩니다. 연속적인 n 개의 최대 합을 찾을 필요가있다.

Question

선형 배열의 경우 연속적인 nos의 최대 합계를 찾는 문제. 쉽습니다. Kadane's Algo.을 사용하면 쉽게 수행 할 수 있습니다. 그러나 배열은 원의 형태로되어 있고 연속적인 nos의 최대 합을 찾아야합니다. 따라서 startindex와 endindex는 배열의 어느 위치 에나있을 수 있습니다. 나는 O(n) 시간에 그것을 해결하는 방법을 얻지 못하고있다.

예 : { 8, 9, -14, 4, 3}.

최대 하위 배열 sum= 4+3+8+9= 24. startindex=3 and endindex=1 (인덱스 배열 없음). 이 문제에 접근하는 방법에 대한 힌트 나 고민을 보내주십시오. 코드가 필요하지 않습니다.

EDIT : 언급 한대로 순환 배열은 동일한 배열 확장과 두 번 비슷합니다. 그러나 Kadane의 Algo를 그 배열에 적용하고 연속적인 nos를 제한하는 방법. < = N

Answer 1

복사 배열 번 { 8, 9, -14, 4, 3, 8, 9, -14, 4, 3},

을 구하여 길이가 원래 원을 초과하지 않는 최대의 부분 배열을 찾을 수있다.

Answer 2

또는 어레이를 복사하는 대신에 0..2n-10..n-1에서 인덱스 변수의 범위를 확장하고 지표로 (x mod n) 대신 x를 사용한다.

Answer 3

1. 개념은 Kadane의 알고리즘에 의해 최대 합을 찾는 것입니다.
2. 그런 다음 요소 합계를 제거하고 배열의 총합에이를 추가하여 Kadane의 알고리즘으로 최소 합을 찾습니다. 단계 1 및 단계에 의해 산출 된 최대 요소보다 인쇄

2.

private static int maxCircularSum(int a[]) { 
    int max_kadane = kadane(a); 
    int max_wrap = 0, i; 
    for (i = 0; i < a.length; i++) { 
     max_wrap += a[i]; // Calculate array-sum 
     a[i] = -a[i]; // invert the array (change sign) 
    } 
    max_wrap = max_wrap + kadane(a); 
    return (max_wrap > max_kadane) ? max_wrap : max_kadane; 
} 
private static int kadane(int[] a) { 
    int max = Integer.MIN_VALUE, sum = 0; 
    for (int k : a) { 
     sum = sum + k; 
     if (sum < 0) { 
      sum = 0; 
     } 
     if (max < sum) { 
      max = sum; 
     } 
    } 
    return max; 
}