53. 最大子序和

Posted on Edited on In , ,
转载自Leet Code

题目描述

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

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

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

我的代码 1 (Timeout)

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class MySolution 
{
    public int maxSubArray(int[] nums) 
    {
        int max = Integer.MIN_VALUE;
    	for (int i=0; i<nums.length; i++)
    	{
            for (int j=i; j<nums.length; j++)
            {
                int sum = 0;
                for (int k=i; k<=j; k++)
                {
                    sum+=nums[k];
                }
                max = (max<sum)?sum:max;
            }
    	}
    	return max;
    }
}

方法一: 动态规划

\(T(N) = O(N)\), \(S(N) = O(N)\)

假设 nums 数组的长度是 n，下标从 0 到 n-1。 sums[i]: 以第i个数nums[i]结尾的 连续子数组最大和； sums[0]显然等于nums[0]；

则我们求的就是max{sums[i]}, 0<=i<n;

如何求每个sums[i]呢？ 考虑每个sums[i]是nums[i]单独成一段，还是在nums[i]的基础上加入sums[i-1]。 即sums[i] = max{nums[i], nums[i]+sums[i-1]}。

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution
{
    public int maxSubArray(int[] nums) 
    {
        int []sums = new int[nums.length];
        int max = Integer.MIN_VALUE;

        for (int i=0; i<nums.length; i++)
        {
            if (i==0) 
                sums[i] = nums[i];
            else
                sums[i] = Math.max(nums[i], nums[i]+sums[i-1]);
            max = Math.max(sums[i], max);
        }
        return max;
    }
}

我的代码 2: 动态规划

\(T(N) = O(N)\), \(S(N) = O(N)\)

假设 nums 数组的长度是 n，下标从0 到 n-1。 sums[i]: 以第i个数nums[i]开头的 连续子数组最大和； sums[n-1]显然等于nums[n-1]；

则sums[i] = max{nums[i], nums[i]+sums[i+1]}。

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MySolution 
{
    public int maxSubArray(int[] nums) 
    {
    	int []sums = new int [nums.length]; 
        int max = Integer.MIN_VALUE;
    	
    	for (int i=sums.length-1; i>=0; i--)
    	{
            if (i==sums.length-1) 
                sums[i] = nums[nums.length-1];
            else
                sums[i] = Math.max(nums[i], nums[i]+sums[i+1]);
            max = Math.max(max, sums[i]);
    	}
    	return max;
    }
}

方法二: 贪心法

\(T(N) = O(N)\), \(S(N) = O(1)\)

从左向右迭代，一个个数字nums[i]加过去，和为sum； 则当前的max=Max{max,sum}.

在nums[i]处，当sum>(=)0时， 认为在下一步i+1时继续使用这个叠加结果会为当前连续最大值带来增益， 因此在通过比较max值确定是否保存当前sum为最大值之后可以继续使用sum。 在nums[i]处，当sum<0时， 若在下一步i+1再使用这个已为负值的叠加结果则会削弱当前连续最大值， 因此不再使用该sum，在通过比较max值确定是否保存当前sum为最大值之后，将其清零并重新从nums[i+1]开始叠加（即重新考虑新的连续子串）。

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution
{
    public int maxSubArray(int[] nums) 
    {
    	int sum = 0; int max = Integer.MIN_VALUE;
    	for (int i=0; i<nums.length; i++)
    	{
            sum+=nums[i];
            max = Math.max(sum, max);
            if (sum<0) sum=0;
    	}
    	return max;
    }
}

方法三: 分治法 (太复杂了且不是最优解)

\(T(N) = O(N)\), \(S(N) = O(logN)\)

这个分治方法类似于「线段树求解 LCIS 问题」的pushUp操作。

我们定义一个操作get(nums, l, r)表示查询nums序列[l, r]区间内的最大子段和， 那么最终我们要求的答案就是get(nums, 0, nums.size() - 1)。

如何分治实现这个操作呢？ 对于一个区间[l, r]，我们取m = ⌊(l + r)/(2)⌋，对区间[l, m]和[m + 1, r]分治求解。

当递归逐层深入直到区间长度缩小为1的时候，递归「开始回升」。 这个时候我们考虑如何通过[l, m]区间的信息和[m + 1, r]区间的信息 合并成区间[l, r]的信息。

最关键的两个问题是： - 我们要维护区间的哪些信息呢？ - 我们如何合并这些信息呢？

对于一个区间[l, r]，我们可以维护四个量： - lSum 表示[l, r]内以l为左端点的最大子段和; - rSum 表示[l, r]内以r为右端点的最大子段和; - mSum 表示[l, r]内的最大子段和; - iSum 表示[l, r]的区间和;

以下简称[l, m]为[l, r]的「左子区间」，[m + 1, r]为[l, r]的「右子区间」。 我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到[l, r]的信息）？

对于长度为1的区间[i, i]，四个量的值都和nums[i]相等。

对于长度大于1的区间： - iSum: 区间[l, r]的iSum就等于「左子区间」的iSum加上「右子区间」的 iSum。 - lSum: 对于[l, r]的 lSum: - 要么等于「左子区间」的 lSum; - 要么等于「左子区间」的iSum 加上「右子区间」的 lSum; 二者取大。 - rSum: 对于[l, r]的rSum: - 要么等于「右子区间」的 rSum; - 要么等于「右子区间」的 iSum 加上「左子区间」的rSum; 二者取大。 - mSum: 考虑 [l, r]的 mSum对应的区间是否跨越 m: - 它可能不跨越 m，也就是说[l, r]的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个; - 它也可能跨越 m，可能是「左子区间」的rSum 和 「右子区间」的 lSum求和; 三者取大。

这样问题就得到了解决。

{.line-numbers}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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-l)/2;
        //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);
    }
}