[알고리즘] Kadane's Algorithm

Kadane's Algorithm

카데인 알고리즘은 최대 부분배열합 문제를 $o(n)$에 해결할 수 있는 알고리즘입니다.

설명

최대 부분배열합 문제를 O(N)으로 풀기 위한 핵심은 각각의 최대 부분합은 이전 최대 부분합이 반영된 결과값입니다.
따라서 각각의 인덱스가 가질 수 있는 최대 부분합을 다이나믹 프로그래밍을 응용하여 해결합니다.
각각의 인덱스 값은 이전 인덱스가 갖고 있는 최대 부분합을 연장할지, 아니면 자신의 값으로 초기화할지 그저 선택을 하면됩니다.

코드

    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        for (int i = 1; i<nums.size(); i++) {
            nums[i] = max(nums[i], nums[i -1] + nums[i]);
            ans = max(nums[i], ans);
        }
        return (ans);
    }