# 2606. Find the Substring With Maximum Cost
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Kadane`
Link: https://leetcode.com/problems/find-the-substring-with-maximum-cost/description/
## 思路
Kadane’s algorithm 求最大subsequence和
currMax记录以当前元素结尾的最大subsequence和
ans记录整个遍历过程的最大subsequence和
## Code

class Solution:
    def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
        scores = [i for i in range(1, 27)]
        for i, c in enumerate(chars):
            scores[ord(c)-ord('a')] = vals[i]
        ans, currMax = 0, 0
        for i in s:
            currMax = max(currMax+scores[ord(i)-ord('a')], scores[ord(i)-ord('a')])
            ans = max(currMax, ans)
        return ans