最大的胜利：求最大子序和

53. 较大子序和(挥剑 Offer 42)

知识要点：二维数组；前缀和；卫兵；动态规划；贪婪；分治算法；

题型叙述

键入一个整形二维数组，二维数组中的一个或持续好几个整数金额构成一个子二维数组。求全部子二维数组的和的最高值。

规定算法复杂度为O(n)。

实例

键入: nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出: 6
表述: 持续子二维数组 [4,-1,2,1] 的和较大，为 6。

打法一：前缀和 卫兵

持续子二维数组 –> 前缀和
过去往后面解析xml求前缀和，保持2个自变量，一个是较大子二维数组和，也就是回答，一个是最少的前缀和，我们可以把这个值了解为卫兵，这一便是大家用于获得回答的，由于每一次前缀和-这一最少的毫无疑问便是较大的。

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0; //前缀和；
        int minPre = 0; //最少的前缀和：卫兵；
        int maxSum = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i  ){
            pre  = nums[i];
            maxSum = Math.max(maxSum, pre-minPre);
            minPre = Math.min(pre, minPre);
        }
        return maxSum;
    }
}

打法二：贪婪

这题贪婪怎么解？贪什么？想一下在这个全过程中，例如-2 1，大家必须-2吗？不用！由于负值只能降低大家最终的和，只起不良反应的干脆比不上不用了。立即从1逐渐就可以了； 贪的便是负值和一定会降低結果。
因此大家的贪婪挑选对策便是：只挑选和>0的，针对和<=0的都能够放弃了。

class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0; i < nums.length; i  ){
            sum  = nums[i];
            maxSum = Math.max(sum, maxSum);
            if(sum <= 0){
                sum = 0; //针对<=0的前缀和，早已没要实际意义了，从下一部位逐渐；
                continue;
            }
        }
        return maxSum;
    }
}

打法三：分治算法

这题可以用分治算法去解。期待去求得一个区段[l,r]内的较大子序和，依照分而治之的观念，能够将其分成左区段和右区段。
左区段L：[l, mid]和右区段R：[mid 1, r].
lSum 表明 [l,r] 内以 l 为左节点的较大子段和
rSum 表明 [l,r] 内以 r 为右节点的较大子段和
mSum 表明 [l,r] 内的较大子段和
iSum 表明 [l,r] 的区段和
递归算法地求得出L.mSum及其R.mSum以后求得M.mSum。因而最先在分治算法的递归算法全过程中必须维护保养区段较大持续子列和mSum这一信息内容。
下面剖析怎样维护保养M.mSum。从总体上有3种很有可能：

• M上的较大持续子列和编码序列彻底在L中，即M.mSum = L.mSum
• M上的较大持续子列和编码序列彻底在R中，即M.mSum = R.mSum
• M上的较大持续子列和编码序列跨过L和R，则该编码序列一定是以L中的某一部位逐渐持续到mid（L的右界限），随后从mid 1（R的左界限）逐渐持续到R中的某一部位。因而大家还必须维护保养区段左界限逐渐的较大持续子列和leftSum及其区段右界限完毕的较大持续子列和rightSum信息内容

class Solution {
    public class Status{
        public int lSum, rSum, mSum, iSum;
        // lSum 表明 [l,r] 内以 l 为左节点的较大子段和
        // rSum 表明 [l,r] 内以 r 为右节点的较大子段和
        // mSum 表明 [l,r] 内的较大子段和
        // iSum 表明 [l,r] 的区段和
        public Status(int lSum, int rSum, int mSum, int iSum){
            this.lSum = lSum;
            this.rSum = rSum;
            this.mSum = mSum;
            this.iSum = iSum;
        }
    }
    public Status getInfo(int[] a, int l, int r){
        if(l == r) return new Status(a[l], a[l], a[l], a[l]); //停止标准；
        int mid = l   ((r-l) >> 1);
        Status lsub = getInfo(a, l, mid);
        Status rsub = getInfo(a, mid 1, r);
        return pushUp(lsub, rsub); 
    }
    //依据2个字符串函数获得全部编码序列結果；
    public Status pushUp(Status l, Status r){
        int iSum = l.iSum   r.iSum;
        int lSum = Math.max(l.lSum, l.iSum r.lSum);
        int rSum = Math.max(r.rSum, r.iSum l.rSum);
        int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum r.lSum);
        return new Status(lSum, rSum, mSum, iSum);
    }

    public int maxSubArray(int[] nums) {
        return getInfo(nums, 0, nums.length-1).mSum;
    }
}

打法四：动态规划

• 1.明确dp二维数组和其下标底含意：dp[i]表明以i末尾的持续子二维数组的较大和；
• 2.明确递推公式，即情况迁移方程式：以i末尾想一下大家有几种很有可能，一种是i-1回来的，也就是上一个的持续子二维数组持续到i处了，那和就为dp[i-1] nums[i],另一种呢，便是自身逐渐，前边那一个持续子二维数组不好，那便是nums[i]了，想一下为何前边那一个不好，还并不是前边的和会连累自身，那么就代表着前边的和是负值；这实际上就引出来贪婪的方式 了。但是大家这儿无需那么不便，立即用一个max函数，取二者大的那一个就可以了；
• 3.dp复位base case：dp[0]只有一个数，因此dp[0] = nums[0];

class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len]; //以i末尾的持续子二维数组的较大和为dp[i];
        if(nums == null || len <= 1) return nums[0];
        dp[0] = nums[0];
        for(int i = 1; i < len; i  ){
            dp[i] = Math.max(dp[i-1] nums[i], nums[i]); //情况迁移；
        }
        //留意我们要解析xml一遍回到较大的dp；
        int maxSum = dp[0];
        for(int i = 1; i < len; i  ){
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }
}

自然以上程序流程能够提升，由于大家的dp[i]实际上只和前一情况i-1相关，因此能够选用一个翻转自变量来纪录，而无需全部二维数组。

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0;  //纪录前一情况；
        int res = nums[0]; //纪录最终結果的最高值；
        for (int num : nums) {
            pre = Math.max(pre   num, num);
            res = Math.max(res, pre);
        }
        return res;
    }
}

感受

这道题型是一道很典型性的题型，使用了各种各样方式 和观念。要常看常做，分治算法是在其中较为艰难的，可是要会这类观念。这道题型最好是的方式 或是卫兵和动态规划， 实际上贪婪就是以动态规划的一个特殊情况以往的，感受二者的关联；