最大子数组和

经典题目：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

注意：题目要求子数组最少包含一个元素，所以返回结果可能为负（若所有元素负，则将返回最大的一个负数）。倘若允许子数组为空（结果为0），则要怎么修改？

示例 1：

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

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

解1 动态规划：

int maxSubArray(vector<int>& nums) {
    if(nums.empty()) return 0;
    size_t n=nums.size();
    vector<int> ans(n); // 代表以nums[i]为结尾的连续最大和
    ans[0]=nums[0];
    for(int i=1;i<n;i++) {
        ans[i]=max(ans[i-1]+nums[i],nums[i]);
    }
    return *max_element(ans.begin(), ans.end());
}

刻画解的状态结构：f(i)代表以nums[i]为结尾的连续最大和
状态转移方程：f(i)=max{ f(i-1)+nums[i], nums[i] }
解释：选择是将nums[i]以nums[i-1]为结尾的最优解，或是选择以nums[i]单独成为解

注：我在第一次尝试解答时，将状态结构f(i)构造为了 代表以nums[1]…num[i]可以包含的最优解，
然而后续遭遇了困难，因为我无法简单确定nums[1]…num[i-1]的最优解位置，可能不在末尾而在中间，难以继续转移。
以后要注意不同的结构构造方法，并且注意怎样构造才更方便更简洁。

解2 分治法：

int maxCrossingSubArray(vector<int>& nums, int left, int mid, int right) {
    int leftSum=0;
    for(int i=mid-1, sum=0; i>=left; i--) {
        sum+=nums[i];
        if(sum > leftSum) {
            leftSum = sum;
        }
    }
    int rightSum=0;
    for(int i=mid+1, sum=0; i<=right; i++) {
        sum+=nums[i];
        if(sum > rightSum) {
            rightSum = sum;
        }
    }
    return leftSum+nums[mid]+rightSum;
}
int maxSubArray(vector<int>& nums, int left, int right) {
    if (left==right) {
        return nums[left]; // base case
    }
    int mid = (left+right)/2;
    int rLeft = maxSubArray(nums, left, mid);
    int rRight = maxSubArray(nums, mid+1, right);
    int rMid = maxCrossingSubArray(nums, left, mid, right);
    return max(max(rLeft, rRight), rMid);
}
int maxSubArray(vector<int>& nums) {
    return maxSubArray(nums, 0, nums.size()-1);
}

注：
maxCrossingSubArray的实现
注意左右的最大和要分开计算。想想若使用同一个sum变量会发生什么？
要注意解中肯定可能包含负数，并非遇到负数就要中断。如3 -1 5肯定比3大。

解3 分治：
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
著作权归作者所有。

struct Status {
    int lSum, rSum, mSum, iSum;
};

Status pushUp(Status l, Status r) {
    int iSum = l.iSum + r.iSum;
    int lSum = max(l.lSum, l.iSum + r.lSum);
    int rSum = max(r.rSum, r.iSum + l.rSum);
    int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
    return (Status) {lSum, rSum, mSum, iSum};
};

Status get(vector<int> &a, int l, int r) {
    if (l == r) {
        return (Status) {a[l], a[l], a[l], a[l]};
    }
    int m = (l + r) >> 1;
    Status lSub = get(a, l, m);
    Status rSub = get(a, m + 1, r);
    return pushUp(lSub, rSub);
}

int maxSubArray(vector<int>& nums) {
    return get(nums, 0, nums.size() - 1).mSum;
}

该解采用了不同的分治设计，具体可以参见LeetCode答案。

Donate