Lesson 9 - SliceSum

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:

A[0] = 3 A[1] = 2 A[2] = -6
A[3] = 4 A[4] = 0
the function should return 5 because:

(3, 4) is a slice of A that has sum 4,
(2, 2) is a slice of A that has sum −6,
(0, 1) is a slice of A that has sum 5,
no other slice of A has sum greater than (0, 1).
Write an efficient algorithm for the following assumptions:

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

---

내 답안

카데인 알고리즘을 통해 풀었는데 다시 상기시키자면

int localSum = A[0];
localSum = Math.max(A[i], localSum + A[i]);

부분합이란 결국 이전 인덱스의 부분합에서 내 값만 더한 것이므로 현재 내 값(A[i])과 부분합 값 중, 큰값을 리턴하면 된다. 현재 내 값과 비교하는 이유는 만약 이전까지의 부분합보다 내가 더 클 경우, 거기서부터 계산하면 되는것이기 때문이다. (솔직히 외우고있다.)

class Solution {
    public int solution(int[] A) {
        if (A.length == 1) {
            return A[0];
        }

        int localSum = A[0];
        int globalSum = A[0];

        for (int i=1; i<A.length; i++) {
            localSum = Math.max(A[i], localSum + A[i]);
            globalSum = Math.max(localSum, globalSum);
        }

        return globalSum;
    }
}