Leetcode 53. maximum-subarray

题目地址：https://leetcode.com/problems/maximum-subarray/description/

题目描述

53.Maximum Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

即找出一个数组里的最大子数组，返回它们的和。

思路

把原数组均分成2部分，然后分3种情况来考虑：

1. 最大子数组完全落在左边的一部分
2. 最大子数组完全落在右边的一部分
3. 最大子数组跨越两个部分

第1、2种情况就是规模更小的相同问题，所以只要考虑第3种情况就行了。
《算法导论》第四章第一小节更详细地分析了这个问题。

代码

class Solution {
public:
    int FindMaxSub(vector<int>& nums,int start,int end){
        if(start==end){
            return nums[start];
        }
        int mid = (start+end)/2;
        int left_max = FindMaxSub(nums,start,mid);
        int right_max= FindMaxSub(nums,mid+1,end);
        int left_mark,right_mark;
        int left_sum=0,right_sum=0;
        int sum1 = -1*INT_MAX;
        for(int i =mid;i >=start;i--){
            left_sum+=nums[i];
            if(left_sum>sum1){
                sum1=left_sum;
                left_mark=i;
            }
        }
        int sum2 = -1*INT_MAX;
        for(int i =mid+1;i <=end ;i++){
            right_sum+=nums[i];
            if(right_sum>sum2){
                sum2=right_sum;
                right_mark=i;
            }
        }
        int x_max= sum1+sum2;
        if(x_max>=left_max && x_max>=right_max){
            return x_max;
        }else if(left_max>=x_max &&left_max>=right_max){
            return left_max;
        }else{
            return right_max;
        }
    }
    
    int maxSubArray(vector<int>& nums) {
        return FindMaxSub(nums,0,nums.size()-1);
    }
};

踩坑

实现代码的过程中WrongAnswer了一次，是因为在子函数 FindMaxSub 里最后判断三种情况的值哪一个值最大的时候没考虑到有可能相等的问题，都只用了>符号，如果出现两个值较大但是相等，而剩下一个值较小的时候反而会返回那个较小的值。