leetcode最大连续子序列（leetcode精选题目）

题：

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

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

示例1:

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6

解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例2:

输入：nums = [1]

输出：1

示例3:

输入：nums = [5,4,-1,7,8]

输出：23

提示：

1 <= nums.length <= 10^5

-10^4 <= nums[i] <= 10^4

解：

方法一：动态规划

假设数组长度为n，用f(i)代表以第i个数结尾的连续子数组的最大和,那么很显然我们要求的就是i在0到n-1之间的f(i)最大值。

求出每个位置的f(i)，然后返回f数组中的最大值即可。因为当前值不确定是加入之前即f(i-1)那段。

可以这样理解，到当前即i的时候，加入的和即f(i)的值都没有自己大，那最大值肯定是自己了，如果f(i)比自己大，那最大肯定就是f(i)了。

到这里只是判断f(i)和i时候的值得大小。还需要再去判断上面的最大值是否有f(i-1)时候的大，有可能自己或者f(i)都没有f(i-1)时候的大。

class Solution {

    public int maxSubArray(int[] nums) {

        int pre = 0, maxAns = nums[0];

        for (int x : nums) {

            pre = Math.max(pre + x, x);

            maxAns = Math.max(maxAns, pre);

        }

        return maxAns;

    }

}

时间复杂度为O(n)，n为数组长度，只需要遍历一遍数组即可。

方法二：分段治理

该方法还是比较复杂的，用了递归，有点绕，我说下我的理解。

定义一个操作get(a,l,r)，表示查询a序列[l,r]区间内的最大子段和。将该区间长度不断右移一位，也就是取中间数，至于为什么不用除以二，因为比如长度3，除以2则为1.5，序列取千1.5很明显有问题，所以采用右移一位。这样当不停递归直到区间长度缩小为1的时候，递归开始回升。

对于一个区间[l,r]，我们可以维护四个量：

• lSum表示[l,r]内以l为左端点的最大子段和，可能是左段的，也有可以是左段区间和加上右端最大子段和

• rSum表示[l,r]内以r为右端点的最大子段和，可能是右段的，也有可能是右段区间和加上左段最大字段和

• mSum表示[l,r]内的最大字段和，存在三种情况，左边最大字段和、右边最大字段和、左边加右边最大字段和，取最大的

• iSum表示[l,r]的区间和

class Solution {

    public class Status {

        public int lSum, rSum, mSum, iSum;

        public Status(int lSum, int rSum, int mSum, int iSum) {

            this.lSum = lSum;

            this.rSum = rSum;

            this.mSum = mSum;

            this.iSum = iSum;

        }

    }

    public int maxSubArray(int[] nums) {

        return getInfo(nums, 0, nums.length - 1).mSum;

    }

    public Status getInfo(int[] a, int l, int r) {

        if (l == r) {

            return new Status(a[l], a[l], a[l], a[l]);

        }

        int m = (l + r) >> 1;

        Status lSub = getInfo(a, l, m);

        Status rSub = getInfo(a, m + 1, r);

        return pushUp(lSub, rSub);

    }

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

    }

}

以[1,2,3,4,5,6]为例，第一次getInfo，l为0，r为5，此时右移一位m是2，那么，先对数组0到2之间依次递归。

那么进来后，l为0，r为2，0+2右移一位为1

那么再进来，此时l为0，r为1，0+1右移一位为0

那么再进来，此时l为0，r为0，则返回a[0]，注意，此时返回后，得到了lSub，还得继续往下走，这个时候的m是0，r是1，进入getInfo方法后返回rSub=a[1]，此时数组都是一个元素，pushUp方法就不讲了，应该很简单。

此时得到的status为lSub，应该还没走完，上面还有一个r为2，m为2的，再进入getInfo得到rSub=a[2]，最后得到左区间的status。

同理右边类似。最后求出结果。

leetcode链接：https://leetcode-cn.com/problems/maximum-subarray/