[ LeetCode ] 53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

Maximum Subarray - LeetCode

풀이 방법

주어진 배열에서 연속된 원소들의 합 중 최대를 구하는 문제이다. Brute force한 방법은, 모든 subarray에 대해 합을 구하고 그 중 최대값을 알아내는 방법인데, 이 방법은 배열의 크기가 N일 때, O(N^2)의 시간복잡도를 가진다. DP를 사용하거나 Divide-and-Conqure 방식으로  풀면 시간복잡도를 줄일 수 있다.

 

 

Dynamic Programming

0~i번째 원소까지 포함한 배열에서 i번째 원소를 포함한 subarray의 최대 합을 라고 하자.

 

(i+1)번째 원소에 대해 생각해보면, 는 둘 중 더 큰 값을 가지는 경우로 결정된다.

• 앞선 subarray에 자신도 포함시키는 경우:  + nums[i+1]
• 자기 자신부터 새로운 subarray를 만드는 경우: nums[i+1]

이를 코드로 나타내면 다음과 같다.

memo[i] = nums[i];
if(memo[i-1] > 0) memo[i] += memo[i-1];

 

이렇게 구한 중, 가장 큰 값을 반환하면 된다. 이 방법으로 풀면 배열의 원소를 각각 한번씩 훑으면 되므로 전체 시간복잡도는 O(N)이다.

 

 

Divide-and-Conquer

2개의 subarray에서 각각 최대 subarray sum을 구한 후, 두 subarray를 합쳤을 때의 subarray sum을 구해나가면 전체 배열의 최대 subsum을 구할 수 있다. 두 배열을 합쳐 최대 subsum을 구하는 방법은 다음과 같다.

 

subsum

각 subarray의 최대 subsum이 위와 같을 때, 두 배열을 합친 배열에서의 subsum은 세가지 경우 중 하나로 결정된다.

1. 왼쪽 subarray의 최대 subsum
2. 오른쪽 subarray의 최대 subsum
3. (왼쪽 subarray의 마지막 원소를 포함한 최대 subsum) + (오른쪽 subarray의 첫번째 원소를 포함한 최대 subsum)

즉, 두개의 subarray를 합치기 위해서는 각 subarray의 첫번째 원소를 포함한 최대 subsum과 마지막 원소를 포함한 최대 subsum을 알아야 한다. 이를 각각 left subsum, right subsum이라 하자.

 

 

left subsum

두 개의 subarray를 합쳤을 때의 left subsum은 두가지 경우 중 하나로 결정된다.

1. 왼쪽 subarray의 left subsum
2. (왼쪽 subarray의 총 합) + (오른쪽 subarray의 left subsum)

 

right subsum

마찬가지로 두 개의 subarray를 합쳤을 때의 right subsum은 두가지 경우 중 하나로 결정된다.

1. 오른쪽 subarray의 right subsum
2. (오른쪽 subarray의 총 합) + (왼쪽 subarray의 right subsum)

---

이를 코드로 구현하기 위해서 우선 배열의 left subsum, right subsum, 최대 subsum, 총 합을 저장하는 구조체를 정의하자.

struct ret{
    int lsum;
    int rsum;
    int subsum;
    int totalsum;
    ret(int l, int r, int s, int t): lsum(l), rsum(r), subsum(s), totalsum(t) {};
};

 

그리고 주어진 배열의 start~end 인덱스 사이의 원소들 중에서 left subsum, right subsum, 최대 subsum, 총 합을 계산하여 ret 구조체로 반환하는 함수 max_subarray()를 다음과 같이 정의하자.

ret max_subarray(vector<int>& nums, int start, int end);

 

max_subarray() 함수에서는 배열을 반으로 나누어 각 subarray에 대해서 ret 구조체를 알아낸다.

int mid = start + (end - start) / 2;
ret left = max_subarray(nums, start, mid);
ret right = max_subarray(nums, mid+1, end);

 

그 후, 위에서 설명한대로 두 subarray를 합친 배열의 ret 구조체를 계산하여 반환한다.

int l = max(left.lsum, left.totalsum + right.lsum);
int r = max(right.rsum, right.totalsum + left.rsum);
int s = max(max(left.subsum, right.subsum), left.rsum + right.lsum);
int t = left.totalsum + right.totalsum;
        
return ret(l, r, s, t);

 

한편, base case에 대해서 생각해보면, 원소가 하나인 배열에 대해서는 left subsum, right subsum, 최대 subsum, 총 합이 모두 해당 원소 값으로 동일할 것이다. 따라서 다음과 같이 base case에 대해서 반환해주자.

if(start == end) return ret(nums[start], nums[start], nums[start], nums[start]);

 

이렇게 Divide-and-Conquer 방식으로 구현하면, 전체 시간복잡도는 O(N)이다. max_subarray() 함수를 총 N번 호출하고, 각 함수는 O(1) 시간에 처리되기 때문이다. 이는 binary tree에서 traversal하는 경우와 유사하다. 한편, 배열을 반으로 쪼개는 과정을 N번 반복할 때 base case가 되므로 공간복잡도는 O(logN)이다.

 

전체 코드는 여기서 확인할 수 있다.