思路:动态规划
dp[i]数组存储以nums[i]结尾的连续子数组最大和。
如果dp[i-1]<0,则dp[i-1]对dp[i]造成负贡献,dp[i]=nums[i];
如果dp[i-1]≥0,则dp[i-1]对dp[i]造成贡献,dp[i]=dp[i-1]+nums[i]。
如果可以修改原数组,可以直接在nums数组上进行修改,将空间复杂度从O(n)降为O(1)
代码如下:
class Solution { public int maxSubArray(int[] nums) { int res = nums[0]; for (int i=1 ; i < nums.length ; i++){ if (nums[i-1] > 0) nums[i] += nums[i-1]; if (res < nums[i]) res = nums[i]; } return res; } }
为什么使用动态规划:
如果暴力法解题,以sum[i,j]表示计算从nums[i]到nums[j]的元素之和,必然会计算以下结果:
sum[0,0] | ||||
sum[0,1] | sum[1,1] | |||
sum[0,2] | sum[1,2] | sum[2,2] | ||
…… | …… | …… | …… |
这样得到的算法时间复杂度是O(n^2)的,不符合题目要求。
如果要进一步优化时间复杂度,观察表格后可以发现
如果每次能在最右侧得到该行的最大值,然后再求这么多最大值的最大值
表格每一行的子数组都是以某一值结尾,所以我们设 dp[i] 为以 i 结尾的子数组的最大值,dp[i] 的最大值就是我们要的结果。
参考:
https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/cong-bao-li-po-jie-dao-dong-tai-gui-hua-yfvkp/