Post

[LeetCode] #53 - Maximum Subarray [Java][C++][Python]

[LeetCode] #53 - Maximum Subarray [Java][C++][Python]

문제 링크


1. 아이디어

합이 가장 큰 연속 부분 배열의 합을 구하는 문제로, 배열을 앞에서부터 보며 각 원소에서 끝나는 부분 배열의 최대 합을 차례로 구한다. 어떤 원소에서 끝나는 부분 배열은 그 원소 하나만 쓰거나 바로 앞 원소에서 끝나는 부분 배열에 이 원소를 이어 붙인 것이다. 이어 붙인 합은 앞 부분 배열의 합에 이 원소를 더한 값이라 앞 합이 클수록 유리하므로, 앞 원소에서 끝나는 부분 배열 중 합이 가장 큰 것 하나만 보면 된다.

그래서 앞의 최대 합이 음수이면 이어 붙일수록 손해라 새로 시작하고 그렇지 않으면 이어 가며, 이렇게 구한 합들 중 최댓값이 답이다. 이 방법이 카데인 알고리즘이다.

부분 배열은 비어 있을 수 없어서 원소가 모두 음수인 배열에서는 가장 큰 원소 하나가 답이 된다. 그래서 답의 초기값을 0으로 두면 틀리고, 가능한 답보다 작은 값에서 시작해야 한다.


2. 코드

풀이 [Java][C++][Python]

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int cur = 0;
        int ans = Integer.MIN_VALUE;
        for (int x : nums) {
            cur = Math.max(x, cur + x);
            ans = Math.max(ans, cur);
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;

class Solution {
   public:
    int maxSubArray(vector<int>& nums) {
        int cur = 0;
        int ans = INT_MIN;
        for (int x : nums) {
            cur = max(x, cur + x);
            ans = max(ans, cur);
        }

        return ans;
    }
};
1
2
3
4
5
6
7
8
9
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        cur = 0
        ans = -1_000_000_000
        for x in nums:
            cur = max(x, cur + x)
            ans = max(ans, cur)

        return ans

원소가 -10,000 이상이라 답도 그 이상이므로, ans의 초기값은 충분히 작은 -1_000_000_000으로 뒀다.


This post is licensed under CC BY 4.0 by the author.