连续子序列优化问题 DP通解

第一题：https://leetcode.com/problems/maximum-subarray/
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
思路：动态规划
子问题定义为 F(A, i) 表示为A[0:i]（前闭后闭）中包含A[i]的最优解
最终问题（A[0:N]中的最优解）的解是子问题解中的最大值

def maxSubArray(self, nums):
        res = maxEndingHere = nums[0]
        for i in range(1, len(nums)):
            maxEndingHere = max(maxEndingHere + nums[i], nums[i]) # maxEnd 定义为包含当前元素的最优解
            res = max(res, maxEndingHere)
        return res

实际上上述解法是连续子序列优化问题的通解
拓展一下
abcefghkk --> efgh
求字符串的最长连续子序列
思路：
遍历
第一步：找到包含当前节点的局部最优解 maxEndHere
第二步：刷新全局最优解 res

def maxLenStr(self, s):
        if not s: return ''
        res = maxEndHere = s[0]
        for i in range(1, len(s)):
            maxEndHere = (maxEndHere if ord(maxEndHere[-1]) + 1 == ord(s[i]) else '') + s[i] # 这里的括号必不可少
            res = maxEndHere if len(maxEndHere) > len(res) else res
        return res