这道题只有一个难点,那就是怎么定义dp[i]
我首先想dpi代表前i项的连续最大和,但这条路走不通,递推方程写不出来
其次想的是dpi代表结果数组大小为i的情况,但也走不通。
一看答案才发现,应该定义dpi为以numsi为结尾的数组
这样确实也是穷举了所有情况,而且非常好写递推
但是确实没那么容易想到
然后自己写的代码如下:
class Solution { public int maxSubArray(int[] nums) { int length=nums.length; int[] dp=new int[length];//从num0到numlength-1 //dpi的意思是以numsi为终点的数组的最大连续和 dp[0]=nums[0]; int currentMax=dp[0]; for(int i=1;i<length;i++) { if(dp[i-1]>=0) {dp[i]=dp[i-1]+nums[i];} else {dp[i]=nums[i];} currentMax=Math.max(currentMax,dp[i]); } return currentMax; } }
但其实还可以优化
于是代码如下:
class Solution { public int maxSubArray(int[] nums) { int res = nums[0]; for(int i = 1; i < nums.length; i++) { nums[i] += Math.max(nums[i - 1], 0); res = Math.max(res, nums[i]); } return res; } }