[알고리즘] 부분수열의 최대합 Maximum Subsequence Sum

Maximum Contiguous Subsequence Sum
n개의 정수 a1, a2, ..., an이 주어졌을 때 연속적인 부분수열의 합이 최대가 되는 구간의 합을 계산하시오.

리트코드 사이트의 문항을 이용해 코드로 연습해보았다.
https://leetcode.com/problems/maximum-subarray/

📍 [방법1] Brute-force

가능한 모든 부분 수열에 대해서 계산을 하고 이 중 가장 큰 합을 찾는다. index i는 부분 수열의 시작 인덱스를, j는 마지막 인덱스를 의미한다. 단순하지만 O(n^3)만큼의 시간복잡도를 가진다. 매우 효율적이지 않다.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int localSum = 0;
        int globalSum = 0;
        int start, end;
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                localSum = 0;
                for(int k=i;k<=j;k++){
                    localSum += nums[k];
                }
                if(localSum>globalSum){
                    start = i; end = j;
                    globalSum = localSum;
                }
            }
        }
        cout<<start<<" "<<end<<endl;
        return globalSum;
    }
};

 

📍 [방법 2] 방법1의 개선

O(n^3)의 시간복잡도를 가지는 브루트포스를 O(n^2)로 개선할 수 있다. i부터 j까지의 부분수열을 계산하는 과정에서 반복문을 사용하지 않고 합을 누적하면서 비교하는 것이다. 다음 숫자 하나만 더 해주면 되므로 다시 처음부터 계산할 필요가 없기 때문이다.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int globalSum = 0;
        int localSum = 0;
        for(int i=0;i<n;i++){
            localSum = 0;
            for(int j=i;j<n;j++){
                localSum += nums[j];
                if(localSum>globalSum){
                    globalSum = localSum;
                }
            }
            
        }
        return globalSum;
    }
};

 

📍 [방법3] 카데인 알고리즘(Kadane's Linear Algorithm)

카데인 알고리즘을 이용하면  O(n)만에 답을 구할 수 있다. 카데인 알고리즘은 DP(동적 프로그래밍)을 이용한 것이다. 너무 헷갈렸다 ....
DP를 이용한 부분은 i번째 원소까지의 최대 합은 (i-1번째 원소까지의 최대합+i번째 원소) 혹은 i번째 원소가 된다는 것이다. ...

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int globalMax = nums[0];
        int localMax = nums[0];
        for(int i=1;i<n;i++){
            localMax = max(nums[i],localMax+nums[i]);
            globalMax = max(globalMax, localMax);

        }
        return globalMax;
    }
};