Kadane’s Algorithm (카데인 알고리즘)

Kadane 알고리즘은 주어진 배열에서 연속된 부분 배열의 합이 가장 큰 값을 효율적으로 찾는 알고리즘. 이 알고리즘은 동적 프로그래밍(Dynamic Programming)의 일종으로, 선형 시간 복잡도 O(n)을 가지기 때문에 큰 배열에서도 빠르게 최대 합을 구할 수 있다.

• 배열의 두 번째 요소부터 마지막 요소까지 반복하면서, 각 요소에서 maxCurrent를 현재 요소와 maxCurrent + 현재 요소 중 더 큰 값으로 갱신
• maxGlobal을 maxCurrent와 비교하여 더 큰 값으로 업데이트

예시

public class KadaneAlgorithm {
    public static int main(String[] args) {
        int[] example = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSum = maxSubArray(example);
        return maxSum;
    }
    
    public static int maxSubArray(int[] nums) {
        int maxCurrent = nums[0];
        int maxGlobal = nums[0];

        for (int i = 1; i < nums.length; i++) {
            maxCurrent = Math.max(nums[i], maxCurrent + nums[i]);
            
            if (maxCurrent > maxGlobal) {
                maxGlobal = maxCurrent;
            }
        }

        return maxGlobal;
    }
}