예제로 배우는 알고리즘 - Kadane 알고리즘

LeetCode 53. Maximum Subarray

 

https://leetcode.com/problems/maximum-subarray/?envType=study-plan-v2&envId=top-interview-150

---

문제 설명

정수 배열 nums가 주어졌을 때 합이 가장 큰 부분 배열을 찾아서 그 합을 반환

 

예시 1

입력 : nums = [-2,1,-3,4,-1,2,1,-5,4]
출력 : 6

설명 :하위 배열 [4, -1, 2, 1]의 합이 가장 큽니다.

예시 2
입력 : nums  = [1]
출력 : 1
설명 : 하위 배열 [1]의 합이 가장 큽니다.
예시 3
입력 : nums = [5,4,-1,7,8]
출력 : 23
설명 : 하위 배열 [5,4,-1,7,8]의 합이 가장 큽니다.

 

제약 조건
1 <= nums.length <= 105
-104 <= nums [i] <= 104

 

---

풀이 전략

1. 완전 탐색으로 모든 구간 합 구하기

• 인덱스 i <= j에 대해 nums[i...j]의 합을 계산
• 세 중첨 루프가 필요하므로 시간복잡도가 O(N³)으로 비효율적

 

2. 누적합을 구한 뒤 모든 구간 합 구하기

• 구간 합을 루프로 매번 구할 필요가 있을까?
• prefix(누적합)을 구한 뒤 구간 합 = prefix[j + 1] - prefix[i]로 계산
• 두 중첩 루프가 필요하므로 시간복잡도가 O(N²),  더 효율적인 방법은 없을까?

3. Kadane 알고리즘(1차원 DP)

• 이전까지의 최대 구간 합이 음수라면 현재 원소에 이어 붙일 필요가 있을까? -> 없다!!!
• 이전 합 + 현재가 손해라면 구간을 새로 시작
  
  • 예시 : nums = [-2,1,-3,4,-1,2,1,-5,4]
  • -2는 1에 붙이면 손해이므로 1부터 구간 새로 시작
  • 1은 -3에 붙이면 이득이므로 지속, 현재 구간합 -2
  • 현재 구간합 -2는 4에 붙이면 손해이므로 4부터 구간 새로 시작
• 시간복잡도가 O(N)으로 효율적, 공간복잡도도 O(1)로 효율적

4. 분할 정복

• 구간 합을 구하는 정보를 유지하면서 한 번의 순회로 해결할 수는 없을까?
  • sum : 현재 구간 전체 합계
  • prefix : 앞에서부터 더했을 때 제일 큰 합
  • suffix : 뒤에서부터 더했을 때 제일 큰 합
  • best : 모든 경우 최대 연속 구간 합(왼쪽 구간 최대, 오른쪽 구간 최대, 왼쪽 구간 뒤 + 오른쪽 구간  앞 이어 붙였을 때)
• 분할 후 병합 시 L.best, R.best, L.suffix + R.prefix 중  가장 큰 값 구하기
  
  • 예시 : nums = [2, -1, 3, -2]
  • 분할 1 : [2, -1] / [3, -2]
  • 왼쪽 분할 및 병합 : [2] / [-1] => sum = 1, prefix = max(2, 2 - 1), suffix = max(-1, -1 + 2), best = 2
  • 오른쪽 분할 및 병합 : [3] / [-2] => sum = 1, prefix = max(3, 3 - 2), suffix = max(-2, -2 + 3), best = 3
  • 분할 1 병합
    • sum = L.sum(1) + R.sum(1) = 2
    • prefix = L.prefix(2), L.sum(1) + R.prefix(3) 중 최대 4
    • suffix = R.suffix(1), R.sum(1) + L.suffix(1) 중 최대 2
    • best = L.best(2), R.best(3), L.suffix(1) + R.prefix(3) 중 최대 4
• 분할 정복은 절반씩 나누므로 재귀 호출의 트리 깊이는 logN, 전체 배열의 크기 N만큼 병합해야 하므로 시간복잡도는 O(NlogN)

---

풀이

Kadane 알고리즘(1차원 DP)

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = 0;
        int best = Integer.MIN_VALUE;

        for (int x : nums) {
            // 이전 합 + 현재가 손해라면 구간을 현재값부터 새로 시작
            cur = Math.max(x, cur + x);
            best = Math.max(best, cur);
        }

        return best;
    }
}

 

분할 정복

class Solution {
    private static class Info {
        // 구간 합, 앞부터 더했을 때 최대, 뒤부터 더했을 때 최대, 헌재 최대 구간 합
        int sum, pref, suff, best;

        Info(int v) {
             sum = pref = suff = best = v; 
        }

        Info(int sum, int pref, int suff, int best) {
            this.sum = sum;
            this.pref = pref;
            this.suff = suff;
            this.best = best;
        }
    }

    public int maxSubArray(int[] nums) {
        return divide(nums, 0, nums.length - 1).best;
    }

    private Info divide(int[] a, int l, int r) {
        if (l == r) return new Info(a[l]);
        int m = l + (r - l) / 2;
        Info left = divide(a, l, m);
        Info right = divide(a, m + 1, r);

        return merge(left, right);
    }

    private Info merge(Info L, Info R) {
        int sum  = L.sum + R.sum;
        int pref = Math.max(L.pref, L.sum + R.pref);
        int suff = Math.max(R.suff, R.sum + L.suff);
        int best = Math.max(Math.max(L.best, R.best), L.suff + R.pref);

        return new Info(sum, pref, suff, best);
    }
}

 

LeetCode 918. Maximum Sum Circular Subarray

 

https://leetcode.com/problems/maximum-sum-circular-subarray/description/?envType=study-plan-v2&envId=top-interview-150

---

문제 설명

길이 n의  원형 정수 배열 nums가 주어졌을 때 비어 있지 않은 수의 부분 배열의 최대 합을 반환

- 원형 배열은 배열의 끝이 배열의 시작 부분에 연결되는 것을 의미

- 부분 배열은 각 요소를 최대 한 번만 포함할 수 있음

 

예시 1

입력 : nums = [1,-2,3,-2]
출력 : 3

설명 :하위 배열 [3]의 합이 가장 큽니다.

예시 2
입력 : nums  = [5,-3,5]
출력 : 10
설명 : 하위 배열 [5, 5]의 합이 가장 큽니다.
예시 3
입력 : nums = [-3,-2,-3]
출력 : -2
설명 : 하위 배열 [-2]의 합이 가장 큽니다.

 

제약 조건

n == nums.length
1 <= n <= 30,000
- 30,000 <= nums [i] <= 30,000

 

---

풀이 전략

1. 완전 탐색으로 모든 구간 합 구하기

• 모든 시작 인덱스 i, 끝 인덱스 j에 대해 nums[i...j]의 합을 계산
• 세 중첨 루프가 필요하므로 시간복잡도가 O(N³)으로 1초 내 실행 불가

 

2. 누적합을 구한 뒤 모든 구간 합 구하기

• 원형 배열을 간단하게 표현할 수는 없을까?
• 자기 자신을 이어 붙인 2n 길이의 배열 만들기(같은 요소는 한번만 사용할 수 있으므로 충분)
• 구간 합을 루프로 매번 구할 필요가 있을까?
• prefix(누적합)을 구한 뒤 구간 합 = prefix[j + 1] - prefix[i]로 계산
• 두 중첩 루프가 필요하므로 시간복잡도가 O(N²)으로 1초 내 실행 불가

3. Kadane 알고리즘(1차원 DP)

• 원형 배열의 최대는 어떤 경우가 있을까?
  • Case 1 : 최대 구간이 한바퀴를 돌지 않음 -> 최대 부분합
  • Case 2 : 최대 구간이 한바퀴를 돔(배열의 시작과 끝을 포함) -> 전체합 - 최소 부분 합
  • 최대 부분합과 최소 부분합은 Kadane 알고리즘을 사용
  • 단, 모든 원소가 음수일 때 Case 2의 경우 항상 0이 되므로 Case 1 결과를 사용해야 함에 주의
• 이전 합 + 현재가 손해라면 구간을 새로 시작
  
  • 예시 : nums = [5, -3, 5]
  • Case 1 : 최대 부분합 5
  • Case 2 : 전체 합(7) - 최소 부분 합(-3) = 10
  • Case1이 더 크므로 Case2의 10이 정답
• 시간복잡도가 O(N)으로 효율적, 공간복잡도도 O(1)로 효율적

---

풀이

Kadane 알고리즘(1차원 DP)

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int maxKadane = Integer.MIN_VALUE, curMax = 0;
        int minKadane = Integer.MAX_VALUE, curMin = 0;
        int total = 0;

        for (int x : nums) {
            // 최대 부분합
            curMax = Math.max(x, curMax + x);
            maxKadane = Math.max(maxKadane, curMax);

            // 최소 부분합
            curMin = Math.min(x, curMin + x);
            minKadane = Math.min(minKadane, curMin);

            total += x;
        }

        // 모두 음수인 경우 처리
        if (total == minKadane) return maxKadane;

        // 한바퀴를 돌지 않는 경우와 도는 경우 중 최대를 반환
        return Math.max(maxKadane, total - minKadane);
    }
}

 

---

팁

• 문제 풀이 :  최대 부분합, 최소 부분합을 요구 -> Kadane 알고리즘
• 실무 활용
  • Kadane 알고리즘 : 최대 손익 구간, 최대 트래픽 구간
  • 원형 패턴 : 순환되는 데이터(24시간, 순환 라운드)