题目
思路1(分析数组的规律)
- 我们可以从头到尾逐个累加,若之前的累加和小于0,那就从丢弃之前的累加,从当前开始重新累加,同时在遍历过程中比较记录下最大值
-
curSum
记为当前最大值,为 0,以[-2,1,-3,4,-1,2,1,-5,4]
为例:- 首先加上 -2,此时
curSum
为 -2 - 由于 -2 小于 0,所以丢弃,然后再加上 1,此时
curSum
为 1 - 再加上 -3,此时
curSum
为 -2 - 由于 -2 小于 0,所以再次丢掉,然后加上 4,此时
curSum
为4 - 然后加上 -1,此时
curSum
为 3 - 再加上 2,此时
curSum
为 5 - 再加上 1,此时
curSum
为 6 - 再加上 -5,此时
curSum
为 1 - 最后再加上最后一个 4,此时
curSum
为 5 - 在这每次遍历中,我们使用一个变量
res
存储最大值,可以找到最大值为 6
- 首先加上 -2,此时
-
代码
class Solution {
public int maxSubArray(int[] nums) {
int length = nums.length;
// 最大总和值
int res = Integer.MIN_VALUE;
// 当前总和
int curSum = 0;
for (int i = 0; i < length; i++) {
if (curSum < 0) {
// 如果 i 之前总和值小于0,那就从 i 开始重新计算
curSum = nums[i];
} else {
// 否则加上当前的值
curSum += nums[i];
}
// 寻找最大值
if (curSum > res) {
res = curSum;
}
}
return res;
}
}
复杂度分析
- 时间复杂度:\(O(N)\)
- 空间复杂度:\(O(1)\)
思路2(动态规划)
-
和思路一差不多动态规划就是利用历史记录,避免重复计算。所以也是从头到尾逐个累加,若之前的累加和小于0,那就从丢弃之前的累加,从当前开始重新累加,我们可以定义一个
dp
数组,dp[i]
代表的意义就是以i
结尾的子数组的最大值。因此我们可以得出状态转移方程:\[dp[i] = \begin{cases} dp[i-1]+nums[i], & \text{if } dp[i-1]<0 \\ nums[i], & \text{if } dp[i-1]\geq0 \end{cases}
\] 既然我们可以得到以
i
结尾子数组的最大值,那么只需要从这些最大值中找到最大的一个就是结果了~
代码
class Solution {
public int maxSubArray(int[] nums) {
int length = nums.length;
int[] dp = new int[length];
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < length; i++) {
dp[i] = dp[i-1] > 0 ? dp[i-1]+nums[i] : nums[i];
res = Math.max(res, dp[i]);
}
return res;
}
}
可以进一步优化:
class Solution {
public int maxSubArray(int[] nums) {
int length = nums.length;
// 记录子数组中的最大值
int res = Integer.MIN_VALUE;
// 记录前一段子数组之和
int preSum = 0;
for (int num : nums) {
// 意思也是判断前一个字数组之和是否小于0
preSum = Math.max(num, preSum + num);
// 然后记录最大值
res = Math.max(res, preSum);
}
return res;
}
}
复杂度分析
- 时间复杂度:\(O(N)\)
- 空间复杂度:\(O(1)\)