題目地址：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.

即找出一個(gè)數(shù)組里的最大子數(shù)組，返回它們的和。

思路

把原數(shù)組均分成2部分，然后分3種情況來考慮：

1. 最大子數(shù)組完全落在左邊的一部分
2. 最大子數(shù)組完全落在右邊的一部分
3. 最大子數(shù)組跨越兩個(gè)部分

第1、2種情況就是規(guī)模更小的相同問題，所以只要考慮第3種情況就行了。
《算法導(dǎo)論》第四章第一小節(jié)更詳細(xì)地分析了這個(gè)問題。

代碼

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);
    }
};

踩坑

實(shí)現(xiàn)代碼的過程中WrongAnswer了一次，是因?yàn)樵谧雍瘮?shù) FindMaxSub 里最后判斷三種情況的值哪一個(gè)值最大的時(shí)候沒考慮到有可能相等的問題，都只用了>符號(hào)，如果出現(xiàn)兩個(gè)值較大但是相等，而剩下一個(gè)值較小的時(shí)候反而會(huì)返回那個(gè)較小的值。