(动态规划) 剑指 Offer 42. 连续子数组的最大和 —

这篇具有很好参考价值的文章主要介绍了(动态规划) 剑指 Offer 42. 连续子数组的最大和 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

难度：简单

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为 O(n)。

示例1:

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

提示：

$1 <= arr.length <= 10^5$
$-100 <= arr[i] <= 100

注意：本题与 53. 最大子数组和相同。

💡思路：动态规划

定义 dp 数组， dp[i]代表以元素 nums[i] 为结尾的连续子数组最大和。

若 dp[i−1] < 0 ，说明 dp[i−1]对 dp[i] 产生负贡献，即 dp[i−1]+nums[i] 还不如 nums[i] 本身大。
- 当 dp[i−1]>=0 时，执行：
  $d p [i] = d p [i - 1] + n u m s [i]$
- 当 dp[i−1]<0 时，执行：
  $d p [i] = n u m s [i]$
初始状态： dp[0]=nums[0]，即以 nums[0] 结尾的连续子数组最大和为nums[0]。

优化：

观察发现 dp[i] 只与 dp[i−1] 和 nums[i] 有关系，因此可以第一个变量 sum 存储 dp[i] 的值，即存储以元素 nums[i] 为结尾的连续子数组最大和。
由于省去 dp 列表使用的额外空间，因此空间复杂度从 $O (n)$ 降至 $O (1)$ 。

🍁代码：(C++、Java)

C++

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num : nums){
            sum = sum < 0 ? num : sum + num;
            ans = max(ans, sum);
        }
        return ans;
    }
};

Java

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num : nums){
            sum = sum < 0 ? num : sum + num;
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}