来源Leetcode第53题最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
这题上课讲过，思路是分治，分越过中点，没有越过中点，又分中点左边，中点右边，共3种情况。
不过写的时候忘记了，于是先采用了万能的循环遍历，在倒数第三个测试用例时TLE了，打扰了
普通解法
用O(n^2)的时间，即2个循环去遍历所有子序列的情况，最终保存最大值即可，方法简单，但是会超时。
坑在于max值的设置，要设置成Integer.MIN_VALUE，以及第2重循环，将上一个子序列的值保留下来。
但是这样的效率非常低，用时62ms，击败了7.70%用户2333.
代码如下：
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 len = nums.length;
int max = Integer.MIN_VALUE ;
if(len == 0) return 0;
for(int i = 0 ; i < len ; i ++ ){
int sum = nums[i];
if(sum > max)
max = sum ;
for(int j = i + 1 ; j < len ;j++){
sum += nums[j];
if(sum > max)
max = sum;
}
}
return max ;
}
}
|
动态规划
思路
- 动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
- 如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
- 如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
- 每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果
[动图(https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/)见
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int maxSubArray(int[] nums) {
int ans = nums[0];
int sum = 0;
for(int num: nums) {
if(sum > 0) {
sum += num;
} else {
sum = num;
}
ans = Math.max(ans, sum);
}
return ans;
}
|
分治
思路见算法导论分治一节
数据结构与算法分析第二章P29
但是运行时间反而不如动态规划啊2333
代码来自：
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
| public int maxSubArray(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
return maxSubArraySum(nums, 0, len - 1);
}
private int maxCrossingSum(int[] nums, int left, int mid, int right) {
int sum = 0;
int leftSum = Integer.MIN_VALUE;
for (int i = mid; i >= left; i--) {
sum += nums[i];
if (sum > leftSum) {
leftSum = sum;
}
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
for (int i = mid + 1; i <= right; i++) {
sum += nums[i];
if (sum > rightSum) {
rightSum = sum;
}
}
return leftSum + rightSum;
}
private int maxSubArraySum(int[] nums, int left, int right) {
if (left == right) {
return nums[left];
}
int mid = (left + right) >>> 1;
return max3(maxSubArraySum(nums, left, mid),
maxSubArraySum(nums, mid + 1, right),
maxCrossingSum(nums, left, mid, right));
}
private int max3(int num1, int num2, int num3) {
return Math.max(num1, Math.max(num2, num3));
}
|