力扣 - 剑指 Offer 42. 连续子数组的最大和

时间:2021-05-09 15:06:15

题目

剑指 Offer 42. 连续子数组的最大和

思路1(分析数组的规律)

  • 我们可以从头到尾逐个累加,若之前的累加和小于0,那就从丢弃之前的累加,从当前开始重新累加,同时在遍历过程中比较记录下最大值
    • curSum记为当前最大值,为 0,以 [-2,1,-3,4,-1,2,1,-5,4] 为例:
      1. 首先加上 -2,此时 curSum 为 -2
      2. 由于 -2 小于 0,所以丢弃,然后再加上 1,此时 curSum 为 1
      3. 再加上 -3,此时 curSum 为 -2
      4. 由于 -2 小于 0,所以再次丢掉,然后加上 4,此时 curSum 为4
      5. 然后加上 -1,此时 curSum 为 3
      6. 再加上 2,此时 curSum 为 5
      7. 再加上 1,此时 curSum 为 6
      8. 再加上 -5,此时 curSum 为 1
      9. 最后再加上最后一个 4,此时 curSum 为 5
      10. 在这每次遍历中,我们使用一个变量 res 存储最大值,可以找到最大值为 6

代码

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)\)