리트코드/leetcode/maxsubarray/부분최대합수열

Divide And Conquer..

int removeDuplicates(vector<int>& nums) {
    int length = 0;
    if(nums.size()==1){
        return 1;
    }
    if(nums.empty()){
        return 0;
    }
    for(int i = 0; i < nums.size() - 1; i++){
        if(nums[i] != nums[i+1]){
            length += 1;
            nums[length] = nums[i+1];
        }
    }
    nums = vector<int>(nums.begin(), nums.begin()+length+1);
    return length+1;
}
Collapse





https://leetcode.com/problems/maximum-subarray/ 
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;
}

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

Maximum Subarray - LeetCode