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

题目剑指 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; } }

【力扣|力扣 - 剑指 Offer 42. 连续子数组的最大和】可以进一步优化：

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; } }

复杂度分析