53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

本题用动态规划是很简单的，动态规划的解题思路就多说了，代码如下：

class Solution {
    public int maxSubArray(int[] nums) {
        int len=nums.length;
        int dp[]=new int [len];
        int max=nums[0];
        int sum=0;
        for (int i=0;i<len;i++)
        {
            sum+=nums[i];
            if(sum>=0)
            {
                if(sum>max)
                {   max=sum;
                    dp[i]=sum;
                }
                else{
                    dp[i]=max;
                }
            }
            else if(sum<0)
            {   
                if(sum>max)
                {   max=sum;
                    dp[i]=sum;
                }
                else{
                    dp[i]=max;
                }
                dp[i]=max;
                sum=0;
            }
        }
        return dp[len-1];
    }
}

关键在于如何用分治法解答出本题，这个我一开始也是没有多少头绪，看了题解才明白，可以用4个变量来记录一段空间里的信息。

• lSum 表示 [l, r]内以 l为左端点的最大子段和
• rSum 表示 [l, r]内以 r 为右端点的最大子段和
• mSum 表示 [l, r]内的最大子段和
• iSum 表示 [l, r] 的区间和
  而通过这四个变量便可以解决本题了，显然我们要得到的就是整个数组的mSum，而如何求得mSum？
  首先要明确一个概念，就是分治算法肯定是需要我们将一段区间分为两个一样大小的部分。那就是前一部分和后一部分。
  mSum可以通过分类讨论是否经过中间点来划分，如果不经过的话那就是，前半部分的mSum和后半部分的mSum更大值，如果经过的话那就是前半部分的rSum加上后半部分的lSum，这三个值经过比较得到的最大值就是mSum。这就是答案了。
  而如何求解lSum和rSum，iSum都是比较简单的部分了，代码如下：

class Solution {
    struct Data{
        int iSum,lSum,rSum,mSum;
    };
public:
    int maxSubArray(vector<int>& nums) {
        return get(nums,0,nums.size()-1).mSum;
    }
    Data get(vector<int>& nums,int left,int right){
        if(left==right) return (Data){nums[left],nums[left],nums[left],nums[left]};
        int mid=(right-left)/2+left;
        Data leftSub = get(nums,left,mid);
        Data rightSub =get(nums,mid+1,right);
        return pushUp(leftSub,rightSub);
    }
    Data pushUp(Data leftSub,Data rightSub){
        int iSum=leftSub.iSum+rightSub.iSum;
        int lSum=max(leftSub.lSum,leftSub.iSum+rightSub.lSum);
        int rSum=max(rightSub.rSum,leftSub.rSum+rightSub.iSum);
        int mSum=max(max(leftSub.mSum,rightSub.mSum),leftSub.rSum+rightSub.lSum);
        return (Data){iSum,lSum,rSum,mSum};
    }
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。