Lesson9. Maximum slice problem - MaxSliceSum

MaxSliceSum - Find a maximum sum of a compact subsequence of array elements.

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

문제 요약

N개의 정수 배열 A가 있고 (P, Q) 0<=P<=Q<N을 A의 slice라고 한다. (P, Q)의 합을 A[P] + A[P+1] + ... + A[Q]라고 할 때, A의 slice의 합 중 최대값을 구해라.

Assume that:

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

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

the result will be an integer within the range [−2,147,483,648..2,147,483,647].

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).

풀이

합의 최대값이므로 양수일 경우에는 계속 더해주면 된다. 단 음수가 나왔을 경우 고려가 필요한데, 음수를 더했을 때 합이 음수가 되면 그 이전까지는 더이상 합에 포함시킬 필요가 없게 된다. 그 앞의 합보다 현재 음수가 더 크고, 합이 음수기 때문에 이후에 포함시켜도 그 만큼 작아지게 된다.

즉 합이 음수가 아닐 때 까지 계속 더하면서 최대값을 구하고, 합이 음수가 되면 그 이전까지의 합은 포함하지 않고 다음 수부터 다시 반복해서 합을 구한다. 예로 [3, 2, -6, 4, 0]이라면 합이 3, 5, -1이 되므로 [2]까지의 최대합은 5이고, 이후 4부터 다시 합을 구하면 4, 0이 된다. 따라서 최대합은 5가 된다.