Lesson9. Maximum slice problem - MaxDoubleSliceSum

MaxDoubleSliceSum - Find the maximal sum of any double slice.

https://app.codility.com/programmers/lessons/9-maximum_slice_problem/max_double_slice_sum/

문제요약

N개의 정수 배열 A가 있고, triplet (X, Y, Z) 0<=X<Y<Z<N은 double slice로 불린다. double slice의 합은 A[X+1] + A[X+2] + ... + A[Y-1] + A[Y+1] + A[Y+2] + ... + A[Z-1]이다. A의 double slice 중 최대 합을 찾아라.

Assume that:

N is an integer within the range [3..100,000];

each element of array A is an integer within the range [−10,000..10,000].

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

풀이

Y를 기준으로 왼쪽과 오른쪽 부분의 합의 최대값을 구한 후 그 두 합이 다시 최대가 되는 값을 찾는다.

즉 왼쪽합 [i]는 i를 포함한 왼쪽의 값들의 합이고 오른쪽합 [i]는 i를 포함한 오른쪽 값들의 합이다. 단, X와 Y 또는 Y와 X를 인접하게 선택하면 각 부분합은 0이되므로 각 부분합은 0보다 작을 수 없다. 각각 구한 후 1부터 N-2까지 반복하면서 각각 왼쪽합[i-1] + 오른쪽합[i+1]의 최대값을 찾는다.