在讨论了最长公共子序列和最长公共子串之后, 可以再考虑一个类似的问题, 给定一个整数序列, 整数序列中含有整数, 负数和 0, 分别求解该整数序列的最长子序列之和 / 最长子串之和, 这也是动态规划算法的两个比较典型的应用

先来看最大子序和, 最大子序和即是要求解给定的整数序列的所有子序列之和的最大值, 考虑将问题拆解, 设 $S_i$ 为整数序列 $a_1, a_2, ... a_i$ 的最大子序和, 不难得出

$$S_{i+1} = \begin{cases} S_i + a_{i+1}, 当 S_i \gt 0\\ a_{i+1}, 其它情况\\ \end{cases}$$

递推初始值:

$$S_0 = a_0$$

于是, 代码实现如下:

package main

import "fmt"

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

func GetLSS(num []int) int {
    result := 0
    dpList := make([]int, len(num))
    for i := 1; i < len(num); i++ {
        dpList[i] = Max(0, dpList[i-1]) + num[i]
        if dpList[i] > result {
            result = dpList[i]
        }
    }
    return result
}

func main() {
    testCase := []int{-1, -2, 3, -2}
    fmt.Println(GetLSS(testCase))
}

最大字段和与最大子序和的差别在于最大子段和计算的是连续元素的最大和, 它的递推关系式与上面完全相同, 只是在代码实现上有差别, 代码如下:

package main

import "fmt"

func MaxSum(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }
    result := 0
    dpList := make([]int, len(nums))
    dpList[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        if dpList[i-1] > 0 {
            dpList[i] = dpList[i-1] + nums[i]
        } else {
            dpList[i] = nums[i]
        }
        if dpList[i] > result {
            result = dpList[i]
        }
    }
    return result
}
func main() {
    testCase := []int{-2, 11, -4, 13, -5, -2}
    fmt.Println(MaxSum(testCase))
}