【Leetcode Daily】2606找到最大开销的字符串

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个字符串和一些字母与数值的对应，要求所有子字符串的最大开销（包括空字符串）

思路分享

• 直接采用动态规划方法，可将求前 i 个元素的最大开销子字符串转化为求前 i-1 个的，状态转移方程为 f[i] = max(0, f[i-1]) + map(s[i])

  https://leetcode.cn/problems/find-the-substring-with-maximum-cost/solutions/2203595/zhuan-huan-zui-da-zi-shu-zu-he-pythonjav-6it2/

• 注意，本题由于可以有空字符串，所以如果还是一维数组，可以留一个位置置零。

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        rec = defaultdict(int)
        # get default valut first
        for i in range(ord('a'), ord('z')+1):
            rec[chr(i)] = i-ord('a')+1
        # print(rec)
        for i, c in enumerate(chars):
            rec[c] = vals[i]
        # print(rec)

        # dynamic plan
        # n = len(s)
        # f = [0] * (n+1)
        # for i in range(n):
        #     f[i+1] = max(0, f[i])+rec[s[i]]
        # return max(f)

        ans = cur = 0
        for c in s:
            cur = max(0, cur) + rec[c]
            ans = max(cur, ans)
        return ans