competitive-programming2022년 2월 16일1분 분량

[LeetCode] 53. Maximum Subarray 풀이

수정일: 2022년 2월 15일

Dynamic programmingDivide and conquer

지원 언어:enko

#Problem

53. Maximum Subarray

#Approach

#Solution 1: DP

왼쪽에서 오른쪽으로 한 번 순회합니다.
nums 배열을 순회하면서, 다음 두 값 중 더 큰 값으로 curSum 값을 갱신합니다.

nums[i]
curSum + nums[i]

정답 maxSum은 모든 curSum 중 최댓값입니다.

#Solution 2: Divide and conquer

부분 배열 nums[L:R]에서의 정답 maxSum을 생각해 봅시다. 이는 다음 세 가지 중 하나입니다.

nums[m]과 nums[m+1] 값을 포함하는 부분 배열의 합 (mMax)
부분 배열 nums[L:m]에서의 maxSum (lMax)
부분 배열 nums[m+1:R]에서의 maxSum (rMax)

우리가 해야 할 일은 다음과 같습니다.

mMax를 계산합니다
왼쪽과 오른쪽 부분 배열에서 maxSum을 구합니다 (재귀 호출)
세 값 중 최댓값을 반환합니다

#Code

#Solution 1: DP

typedef vector<int> vi;

class Solution {
private:
    const int NEG_INF= -1e5;
public:
    int maxSubArray(vi &nums) {
        int n= nums.size(), ans= NEG_INF, curSum= NEG_INF;
        for (int i=0; i < n; ++i) {
            curSum= max(nums[i], curSum+nums[i]);
            ans= max(ans, curSum);
        }
        return ans;
    }
};

#Solution 2: Divide and conquer

typedef vector<int> vi;

class Solution {
private:
    int maxSum(vi &nums, int L, int R) {
        if (L >= R) return nums[L];
        int m= L-(L-R)/2;
        // calculate maxSubarray containing nums[m] to the left
        int mMaxL= nums[m], lSum= nums[m];
        for (int i=m-1; i >= L; --i) {
            lSum += nums[i];
            mMaxL= max(mMaxL, lSum);
        }
        // calculate maxSubarray containing nums[m+1] to the right
        int mMaxR= nums[m+1], rSum= nums[m+1];
        for (int i=m+2; i <= R; ++i) {
            rSum += nums[i];
            mMaxR= max(mMaxR, rSum);
        }
        int mMax= mMaxL+mMaxR;
        return max( mMax, max( maxSum(nums, L, m), maxSum(nums, m+1, R) ) );
    }

public:
    int maxSubArray(vi &nums) {
        int n= nums.size();
        return maxSum(nums, 0, n-1);
    }
};