LeetCode【面试题 16.17. 连续数列】
itaot 人气:1题目描述
给定一个整数数组(有正数有负数),找出总和最大的连续数列,并返回总和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
解题方案一 (动态规划)
思路
假设数组名称为arr,结果数组为result
- 当只有一个数字的时候,最大的连续数列只能是这个数字,所以序号为0的位置,最大值为-2,则有
result[0] = arr[0]
- 当有两个数字时,有两种情况
- 保留前边的序列,此时值为
result[0] + arr[1]=
- 不保留前边的序列,此时值为
1
,即arr[1] - 此时选取最大值的话为1
- 保留前边的序列,此时值为
- 到第三个数字时
- 保留前边的序列,值为
result[1] + arr[2] = 1 + -3 = -2
- 不保留前边的序列,值为
arr[2] = -3
- 此时选取最大值的话为-3
- 保留前边的序列,值为
- 以此类推的话可以得到下表
序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|---|
数值(arr数组) | -2 | 1 | -3 | 4 | -1 | 2 | 1 | -5 | 4 |
保留前边的序列 | -1 | -4 | -1 | 3 | 5 | 6 | 1 | 5 | |
不保留前边的序列 | 1 | -3 | 4 | 4 | 2 | 1 | -5 | 4 | |
最大值(result数组) | -2 | 1 | -3 | 4 | 4 | 5 | 6 | 1 | 4 |
- 总结可得如下规律
- 最终只需取得result[]中值最大的数即为结果
代码
public static int maxSubArray(int[] arrs) {
int len = arrs.length;
int maxNum = arrs[0];
int[] result = new int[arrs.length];
result[0] = maxNum;
for (int i = 1; i < len; i++) {
int a = result[i - 1] + arrs[i]; //保留前边的序列
int b = arrs[i]; //不保留前边的序列
int curMax = Math.max(a, b);
result[i] = curMax;
if (curMax > maxNum) {
maxNum = curMax;
}
}
return maxNum;
}
代码优化
由于上述过程中,创建了result数组,但是实际上每次循环时,当前数字计算完之后就没有其他用处了,所以此处可以使用arrs数组作为result数组来用,优化后如下
public static int maxSubArray(int[] arrs) {
int len = arrs.length;
int maxNum = arrs[0];
for (int i = 1; i < len; i++) {
int a = arrs[i - 1] + arrs[i]; //保留前边的序列
int b = arrs[i]; //不保留前边的序列
int curMax = Math.max(a, b);
arrs[i] = curMax;
if (curMax > maxNum) {
maxNum = curMax;
}
}
return maxNum;
}
加载全部内容