算法篇：动态规划(二)

灰子学技术

发布于 2020-10-30 14:43:39

2370

发布于 2020-10-30 14:43:39

文章被收录于专栏：灰子学技术灰子学技术

算法：

本篇属于动态规划的进阶题目，我们可以通过数据dp[i]来表示包括第i个元素的计算和，然后计算出所有的dp[i],最终求出来最大值就可以。详细见下面的例子中的讲解。

备注：基本公式：f(i) = max(f(i-1),nums[i])

题目1: https://leetcode-cn.com/problems/maximum-subarray/

代码实现：

func maxSubArray(nums []int) int {
     if len(nums) == 0 {
         return 0
     }
     dp := make([]int,len(nums))
     dp[0] = nums[0]
     m := dp[0]
     for i :=1; i< len(nums);i++ {
         if dp[i-1] >= 0 {
             dp[i] = dp[i-1]+nums[i]
         } else {
             dp[i] = nums[i]
         }
         m = max(m,dp[i])
     }
     return m
}
func max(a,b int) int {
    if a>b {
        return a
    }
    return b
}
// dp[i]：表示以 nums[i] 结尾的连续子数组的最大和
// 那么 dp[i]有两种可能:
// 一种dp[i] = dp[i-1]+nums[i](dp[i-]>=0);
// 另一种dp[i] = nums[i](dp[i-1]<0)
// 依次遍历这个数组，依次求dp[i],然后求最大值就好了

执行结果：

题目2:

https://leetcode-cn.com/problems/maximum-product-subarray/

代码实现：

// 算是题目1的变形题目，不同的地方在于：
// 由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin。
// 公式：
// maxF[i] = max(nums[i]*maxF[i-1],max(nums[i],nums[i]*minF[i-1]))
// minF[i] = min(nums[i]*minF[i-1],min(nums[i],nums[i]*maxF[i-1]))
func maxProduct(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    maxA := nums[0]
    minA := nums[0]
    m := nums[0]
    for i:=1;i<len(nums);i++ {
        xA,nA := maxA,minA
        maxA = max(nums[i]*xA,max(nums[i],nums[i]*nA))
        minA = min(nums[i]*nA,min(nums[i],nums[i]*xA))
        m = max(maxA,m)
    }
    return m
}

func max(a,b int) int {
    if a>b {
        return a
    }
    return b 
}
func min(a,b int) int {
    if a>b {
        return b
    }
    return a 
}

执行结果：