贪心，动态规划的区别

题目（力扣53）：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。

示例：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

使用贪心算法：

1. 贪心找的就是局部最优解，当前“连续和”为负数或零的时候就立马放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
2. 局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

 var maxSubArray = function(nums) {
    let result = -Math.pow(10,4)
    let count = 0
    for(let i=0;i<nums.length;i++){
        count += nums[i]
        result = Math.max(count,result)
        //用count来计算，一旦count为负数就立马放弃，寻找下一个子字符串
        count<=0?count=0:''
    }
    return result
};
1
2
3
4
5
6
7
8
9
10
11

使用动态规划：

1. 确定dp数组以及下标的含义
   • dp[i] : 包括下标 i 之前的最大连续子序列之和
2. 确定状态转化公式
   • dp[i-1]>0 : dp[i] = dp[i-1]+nums[i] 当前面的和大于零时，加进来
   • dp[i-1]<=0 : dp[i] = nums[i] 当前面的和小于等于零是 ， 舍弃
3. dp数组的初始化
   • 由于我们是从前往后遍历，所以需要设置dp[0] = nums[0]
4. 遍历的顺序
   • 递推公式中dp[i]依赖于dp[i - 1]的状态，需要从前向后遍历。
     

var maxSubArray = function(nums) {
    let dp = []
    dp[0] = nums[0]
    for(let i=1;i<nums.length;i++){
        if(dp[i-1]>0){
            dp[i] = nums[i]+dp[i-1]
        }else{
            dp[i] = nums[i]
        }
    }
    return  dp.sort((a,b)=>a-b).pop()
};

1
2
3
4
5
6
7
8
9
10
11
12
13