리트코드/Leetcode/부분수열의 최댓값

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

Maximum Subarray - LeetCode

Divide and Conquer / Time Complexity: O(nlogn)

int solution(vector<int> & nums, int l, int r){
    if(l==r) return nums[l];
    int m = (l+r)/2;
    int left_sum = nums[m];
    int sum = 0;
    int right_sum = nums[m+1];
    
    //left Max Sum
    for(int i = m; i >= l; i--){
        sum = sum + nums[i];
        if(sum > left_sum){
            left_sum = sum;
        }
    }
    sum = 0;
    //Right Max Sum
    for(int j = m+1; j <= r; j++){
        sum = sum + nums[j];
        if(sum > right_sum){
            right_sum = sum;
        }
    }
    int crossMaxSum = max(max(left_sum + right_sum, left_sum),right_sum) ;
    return max(max(crossMaxSum, solution(nums, l, m)), solution(nums, m+1, r));
}
​
int maxSubArray(vector<int>& nums) {
    int r = nums.size()-1;
    int l = 0;
    if (r==0) return nums[0];
    int answer = solution(nums, l, r);
    return answer;
}