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

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

 

思路:动态规划

  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] 的最大值就是我们要的结果。

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

 

参考:

  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/

 

 

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


下一篇:42.