题面
输入一个整型数组,数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为 $O(n)$ 。
样例
1 | 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] |
1 | 1 <= arr.length <= 10^5 |
思路
状态定义:$dp[i]$ = 以$nums[i]$为结尾的连续子数组的和的最大值
转移方程:若 $dp[i-1] \leq 0$ ,说明 $dp[i−1]$ 对 $dp[i]$ 产生负贡献,即 $dp[i-1] + nums[i]$ 还不如 $nums[i]$ 本身大。
当 $dp[i-1] \leq 0$,$dp[i]=nums[i]$
当 $dp[i-1]>0$,$dp[i] = dp[i-1]+nums[i]$
代码
1 | int maxSubArray(vector<int>& nums) { |