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

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

 

 

这道题只有一个难点,那就是怎么定义dp[i]

我首先想dpi代表前i项的连续最大和,但这条路走不通,递推方程写不出来

其次想的是dpi代表结果数组大小为i的情况,但也走不通。

一看答案才发现,应该定义dpi为以numsi为结尾的数组

这样确实也是穷举了所有情况,而且非常好写递推

但是确实没那么容易想到

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

 

 然后自己写的代码如下:

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;
    }
}

但其实还可以优化

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

 

 于是代码如下:

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;
    }
}

 

上一篇:Taro+react开发(42)tab栏样式


下一篇:42:漏洞发现-操作系统之漏洞探针类型利用修复