53. 最大子数组和

难度: 中等

来源: 每日一题 2023.07.20 延伸

---

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23
``` 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

```Java
class Solution {
    public int maxSubArray(int[] nums) {

    }
}

分析与题解

---

• 动态规划

  这个题目算是动态规划入门级别的问题了, 整体来说比较简单, 我们使用 dp[i] 代表当前 第 i 个元素的子数组最大值, 那么 dp[i] 只有两种情况

  • 只取 num[i] (最少要有一个元素)

  • 取 num[i] + dp[i -1]

  • 两者取最大即可.

  

  代码如下所示.

  class Solution {
      public int maxSubArray(int[] nums) {
          int length = nums.length;
          int[] dp = new int[length];
          dp[0] = nums[0];
          int result = nums[0];
          for(int i = 1; i < length; i++) {
              dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);
              result = Math.max(dp[i], result);
          }
          return result;
      }
  }
  

  复杂度分析:

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

  结果如下所示.