53. Maximum Subarray - 카데인 알고리즘

문제를 해설할 때 특수한 DP로 카데인을 자주 언급하게 되는데,
카데인 알고리즘이 정확히 어떤 이점이 있는지, 다른 DP와는 무엇이 다른지 명확히 설명한 글이 없어 이렇게 글을 작성한다.

---

 

핵심 아이디어는 다음과 같다.

• dp[i]: 반드시 i에서 끝나는 최대 부분 배열 합

즉, 한쪽 끝을 고정함으로써 중간의 연산을 최적 부분구조 + 중복 부분 문제의 형태로 만드는 아이디어가 핵심이다.

 

 

그러면 이 문제에서 전체 정답은 max_i dp[i] 가 된다.

마지막 원소 a[i]를 포함해야 하므로 두 선택지뿐이다.

1. a[i] 혼자로 새로 시작한다.
2. i−1에서 끝나는 최적해 dp[i−1]에 a[i]를 이어붙인다.

따라서 점화식은 다음과 같다.

• 초기값

이 점화식은 “끝이 i인 최적해”의 정의에서 바로 나온다.

아이디어

• 임의의 최적 부분 배열 [l, r]을 생각해보자.
• 그 배열의 오른쪽 끝 r에서의 localMax[r]는 반드시 그 구간 [l, r]의 합 이상이 된다.
  • localMax[r]는 nums[r]부터 시작하는 선택지와 이전 최적값을 연장하는 선택지를 모두 고려하고 있다.
  • 즉, '이전의 값들이 도움이 되면 가져가고, 도움이 되지 않으면 버린다'라는 전략이 처음부터 진행되면, 항상 최댓값을 갖는 상태만을 가지고 있을 수 있게 된다.
• 따라서 globalMax는 [l, r] 같은 진짜 최적해를 포함해서 항상 최댓값을 담게 된다.

class Solution {
    public int maxSubArray(int[] nums) {
        int ret = nums[0];
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        for(int i = 1; i < n; i++){
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            ret = Math.max(dp[i], ret);
        }
        return ret;
    }
}

좀 더 형식적인 정보는 2023년에 카데인 본인이 발표한 '카데인 알고리즘' 논문을 참고 바란다.

Two Kadane Algorithms for the Maximum Sum Subarray Problem