Kadane: 배열에서 최대 연속 부분 배열 합 구하기

Kadane의 알고리즘은 배열에서 최대 연속 부분 배열 합을 찾는 효율적인 알고리즘이다. 이 알고리즘은 단일 반복문으로 배열을 한 번만 통과하여 시간 복잡도 O(n)을 갖는다.

알고리즘 동작 원리

1. 현재까지의 부분 배열 합을 추적한다.
2. 현재까지의 최대 부분 배열 합을 유지한다.
3. 각 요소를 반복하면서 현재까지의 부분 배열 합을 업데이트하고, 최대 부분 배열 합을 계속해서 갱신한다.

public class Solution {

    public int maxSubArraySum(int[] arr) {
        // 현재까지의 부분 배열 합
        int maxEndingHere = arr[0];
        // 현재까지의 최대 부분 배열 합
        int maxSoFar = arr[0];

        for (int i = 1; i < arr.length; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }

        return maxSoFar;
    }
}