题目描述
给定一个整数数组，找到一个具有最大和的子数组，返回其最大和。
思路
贪心。每次访问的元素，判断其是否应该在子数组中，分这两种情况处理。
用curMax[i]表示访问到nums[i]时，子数组最大的和。
讨论：
- 当curMax[i]+nums[i+1] < 0，curMax[i+1]=0，因为nums[i+1]一定不在最大子数组里，置零不要让其影响之后的curMax[i]的计算
- 当curMax[i]+nums[i+1] >= 0，更新curMax[i+1]，并判断是否要更新最大子数组的和。
虽然nums[i+1]可能是负数，但只要curMax[i+1]是正的，则其仍可能作为最大子数组的一部分！
上面的讨论其实在假设curMax[i]>=0时绝对是正确的，所以可以做一些预处理：
- 找到第一个大于等于0的nums[i]的下标i，从这里开始运用动态规划
- 同时，用一个变量表示数组的最大值，如果数组全是负数，输出这个最大值即可
代码
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
| public int maxSubArray(int[] nums) {
int start = 0;
int exception = nums[0]; // 如果全负，返回最大值
for(int i = 0; i < nums.length; i++) {
if(nums[i] > exception) {
exception = nums[i];
}
if(nums[i] >= 0) {
start = i;
break;
}
}
if(start == nums.length-1) { // 如果全负数，返回最大值
return exception;
}
int res = nums[start]; // 保存子数组最大值
int[] curMax = new int[nums.length]; // 表示当前位置的子数组最大值
curMax[start] = nums[start];
for(int i = start+1; i < nums.length; i++) {
int tmp = curMax[i-1]+nums[i];
if(tmp < 0) {
curMax[i] = 0; // 别影响后面的
}else { // 如果大于0，更新curMax[i]
curMax[i] = tmp;
if(res < curMax[i]) {
res = curMax[i];
}
}
}
return res;
}
|
考察点