#53. 最大子序和

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

示例:

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

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

#写在前面

美团二面的笔试题，自己当时真的一点思路都没有，没做出来，主要是O(n)时间复杂度的限制，再加上我脑子里的动态规划一直都是，从i到j的最大和，结果就把自己绕在那里出不来了。

但其实，如果当时知道了思路，真的就是一道，如力扣所说的，一道简单难度的题 😭

#动态规划

思路是用二维数组来存局部的和，这样不必每次都算一次

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
class Solution {
	public int maxSubArray(int[] nums) {
		int n = nums.length;
		int max = Integer.MIN_VALUE;
		int[][] dp = new int[n][n];
		for (int i = 0; i < n; i++) {
			dp[i][i] = nums[i];
			if (max < nums[i]) {
				max = nums[i];
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				dp[i][j] = dp[i][j - 1] + nums[j];
				if (dp[i][j] > max) {
					max = dp[i][j];
				}
			}
		}
		return max;
	}

	void test() {
		int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
		System.out.println(maxSubArray(nums));
	}
}

但是这个代码，连测试用例都跑不过，超出内存限制。

#降低空间复杂度

首先观察代码，其实d[i][j]只与d[i][j-1]有关，所以只需使用一个一维数组，即可满足存储任务。

进而，d[i][j]本质上只与前一个数有关，那么其实只需用一个值去存前一个值即可。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
	public int maxSubArray(int[] nums) {
		int n = nums.length;
		int max = Integer.MIN_VALUE;

		for (int i = 0; i < n; i++) {
			int t = 0;
			for (int j = i; j < n; j++) {
				t += nums[j];
				if (t > max) max = t;
			}
		}
		return max;
	}

	void test() {
		int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
		System.out.println(maxSubArray(nums));
		System.out.println(maxSubArray(new int[]{1}));
	}
}
1
2
3
Success:
Runtime:137 ms, faster than 5.09% of Java online submissions.
Memory Usage:40.1 MB, less than 5.10% of Java online submissions.

通过了是通过了，但是这题本质上是需要O(n)时间复杂度求解的，很明显，没有达到要求。

#降低时间复杂度

如果前面的数贡献为正的，那么我们的最大值就是前面的数加上当前的数，如果前面的数是负的，那么如果当前的值比前面的数还大，那证明前面的“工作”还不如当前一个人的工作来得多，那前面所有人的工作都可以被当前的人所替代。

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
class Solution {
	public int maxSubArray(int[] nums) {
		int n = nums.length;
		int max = Integer.MIN_VALUE;
		int pre = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			if (pre < 0 && pre < nums[i]) {
				pre = nums[i];
			} else {
				pre += nums[i];
			}
			if (pre > max) {
				max = pre;
			}
		}
		return max;
	}

	void test() {
		int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
		System.out.println(maxSubArray(nums));
		System.out.println(maxSubArray(new int[]{1}));
		System.out.println(maxSubArray(new int[]{1, 2}));
	}
}
1
2
3
Success:
Runtime:1 ms, faster than 95.99% of Java online submissions.
Memory Usage:40 MB, less than 17.17% of Java online submissions.

#官方解答

假设 nums 数组的长度是 n，下标从 0 到 n - 1。

我们用 ai 代表 nums[i]，用 f(i) 代表以第 i 个数结尾的「连续子数组的最大和」，那么很显然我们要求的答案就是：

$$ \begin{aligned} \max\_{0 \leq i \leq n-1}\{f(i)\} \end{aligned} $$

因此我们只需要求出每个位置的 f(i)，然后返回 f 数组中的最大值即可。那么我们如何求 f(i) 呢？我们可以考虑 a_i 单独成为一段还是加入 f(i - 1) 对应的那一段，这取决于 a_i 和 f(i - 1) + a_i 的大小，我们希望获得一个比较大的，于是可以写出这样的动态规划转移方程：

$$ \begin{aligned} f(i)=\max\{f(i-1)+a_i,a_i\} \end{aligned} $$

不难给出一个时间复杂度 O(n)、空间复杂度 O(n) 的实现，即用一个 f 数组来保存 f(i) 的值，用一个循环求出所有 f(i)。考虑到 f(i) 只和 f(i - 1) 相关，于是我们可以只用一个变量 pre 来维护对于当前 f(i) 的 f(i - 1) 的值是多少，从而让空间复杂度降低到 O(1)，这有点类似「滚动数组」的思想。

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 max = nums[0];
		int pre = 0;
		for(int n:nums){
			pre = Math.max(pre+n,n);
			max = Math.max(pre,max);
		}
		return max;
	}

	void test() {
		int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
		System.out.println(maxSubArray(nums));
		System.out.println(maxSubArray(new int[]{1}));
		System.out.println(maxSubArray(new int[]{1, 2}));
	}
}
1
2
3
Success:
Runtime:1 ms, faster than 95.99% of Java online submissions.
Memory Usage:39.6 MB, less than 85.18% of Java online submissions.

#分治

我们定义一个操作 get(a, l, r) 表示查询 a 序列 [l, r] 区间内的最大子段和，那么最终我们要求的答案就是 get(nums, 0, nums.size() - 1)。如何分治实现这个操作呢？对于一个区间 [l, r]，我们取 $$m=\lfloor\frac{l+r}{2}\rfloor$$ ，对区间 [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]，四个量的值都和 ai 相等。对于长度大于 1 的区间：

  • 首先最好维护的是 iSum，区间 [l, r] 的 iSum 就等于「左子区间」的 iSum 加上「右子区间」的 iSum。
  • 对于 [l, r] 的 lSum，存在两种可能，它要么等于「左子区间」的 lSum，要么等于「左子区间」的 iSum 加上「右子区间」的 lSum，二者取大。
  • 对于 [l, r] 的 rSum，同理，它要么等于「右子区间」的 rSum，要么等于「右子区间」的 iSum 加上「左子区间」的 rSum，二者取大。
  • 当计算好上面的三个量之后，就很好计算 [l, r] 的 mSum 了。我们可以考虑 [l, r] 的 mSum 对应的区间是否跨越 m——它可能不跨越 m，也就是说 [l, r] 的 mSum 可能是「左子区间」的 mSum 和 「右子区间」的 mSum 中的一个；它也可能跨越 m，可能是「左子区间」的 rSum 和 「右子区间」的 lSum 求和。三者取大。

这样问题就得到了解决。

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
class Solution {
	public int maxSubArray(int[] nums) {
		return get(nums, 0, nums.length - 1).mSum;
	}

	Status get(int[] nums, int l, int r) {
		if (l == r) return new Status(nums[l], nums[l], nums[l], nums[l]);
		int mid = (l + r) >> 1;
		Status lSub = get(nums, l, mid);
		Status rSub = get(nums, mid + 1, r);
		int iSum = lSub.iSum + rSub.iSum;
		int lSum = Math.max(lSub.iSum + rSub.lSum, lSub.lSum);
		int rSum = Math.max(rSub.iSum + lSub.rSum, rSub.rSum);
		int mSum = Math.max(Math.max(lSub.mSum, rSub.mSum), lSub.rSum + rSub.lSum);
		return new Status(lSum, rSum, mSum, iSum);
	}

	void test() {
		int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
		System.out.println(maxSubArray(nums));
		System.out.println(maxSubArray(new int[]{1}));
		System.out.println(maxSubArray(new int[]{1, 2}));
	}

	class Status {
		int lSum, rSum, mSum, iSum;

		Status(int lSum, int rSum, int mSum, int iSum) {
			this.lSum = lSum;
			this.rSum = rSum;
			this.mSum = mSum;
			this.iSum = iSum;
		}
	}
}
1
2
3
Success:
Runtime:1 ms, faster than 95.99% of Java online submissions.
Memory Usage:39.9 MB, less than 30.01% of Java online submissions.

#完整代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
package xyz.onns.leetcode;

/**
 * @Author Onns
 * @Date 2020/9/13 11:10 AM
 * @Version 1.0
 * @Website https://onns.xyz/blog/
 */
public class MaximumSubarray {
	public static void main(String[] args) {
		new MaximumSubarray().new Solution().test();
	}

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

		Status get(int[] nums, int l, int r) {
			if (l == r) return new Status(nums[l], nums[l], nums[l], nums[l]);
			int mid = (l + r) >> 1;
			Status lSub = get(nums, l, mid);
			Status rSub = get(nums, mid + 1, r);
			int iSum = lSub.iSum + rSub.iSum;
			int lSum = Math.max(lSub.iSum + rSub.lSum, lSub.lSum);
			int rSum = Math.max(rSub.iSum + lSub.rSum, rSub.rSum);
			int mSum = Math.max(Math.max(lSub.mSum, rSub.mSum), lSub.rSum + rSub.lSum);
			return new Status(lSum, rSum, mSum, iSum);
		}

		void test() {
			int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
			System.out.println(maxSubArray(nums));
			System.out.println(maxSubArray(new int[]{1}));
			System.out.println(maxSubArray(new int[]{1, 2}));
		}

		class Status {
			int lSum, rSum, mSum, iSum;

			Status(int lSum, int rSum, int mSum, int iSum) {
				this.lSum = lSum;
				this.rSum = rSum;
				this.mSum = mSum;
				this.iSum = iSum;
			}
		}
	}

	class Solution4 {
		public int maxSubArray(int[] nums) {
			int max = nums[0];
			int pre = 0;
			for (int n : nums) {
				pre = Math.max(pre + n, n);
				max = Math.max(pre, max);
			}
			return max;
		}

		void test() {
			int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
			System.out.println(maxSubArray(nums));
			System.out.println(maxSubArray(new int[]{1}));
			System.out.println(maxSubArray(new int[]{1, 2}));
		}
	}

	class Solution3 {
		public int maxSubArray(int[] nums) {
			int n = nums.length;
			int max = Integer.MIN_VALUE;
			int pre = Integer.MIN_VALUE;
			for (int i = 0; i < n; i++) {
				if (pre < 0 && pre < nums[i]) {
					pre = nums[i];
				} else {
					pre += nums[i];
				}
				if (pre > max) {
					max = pre;
				}
			}
			return max;
		}

		void test() {
			int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
			System.out.println(maxSubArray(nums));
			System.out.println(maxSubArray(new int[]{1}));
			System.out.println(maxSubArray(new int[]{1, 2}));
		}
	}

	class Solution2 {
		public int maxSubArray(int[] nums) {
			int n = nums.length;
			int max = Integer.MIN_VALUE;

			for (int i = 0; i < n; i++) {
				int t = 0;
				for (int j = i; j < n; j++) {
					t += nums[j];
					if (t > max) max = t;
				}
			}
			return max;
		}

		void test() {
			int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
			System.out.println(maxSubArray(nums));
			System.out.println(maxSubArray(new int[]{1}));
		}
	}

	class Solution1 {
		public int maxSubArray(int[] nums) {
			int n = nums.length;
			int max = Integer.MIN_VALUE;
			int[][] dp = new int[n][n];
			for (int i = 0; i < n; i++) {
				dp[i][i] = nums[i];
				if (max < nums[i]) {
					max = nums[i];
				}
			}
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					dp[i][j] = dp[i][j - 1] + nums[j];
					if (dp[i][j] > max) {
						max = dp[i][j];
					}
				}
			}
			return max;
		}

		void test() {
			int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
			System.out.println(maxSubArray(nums));
		}
	}
}

#参考链接