2606. 找到最大开销的子字符串
| 题目链接 | 2606. 找到最大开销的子字符串 |
|---|---|
| 思路 | 前缀和/动态规划-最长子数组和-简单变体 |
| 题解链接 | 【转换】最大子数组和（Python/Java/C++/Go） |
| 关键点 | 无 |
| 时间复杂度 | \(O(n)\) |
| 空间复杂度 | \(O(1)\) |
代码实现（动态规划）：
class Solution:
def maximumCostSubstring(self, s: str, chars: str, vals: List[int]) -> int:
dct = dict(zip(ascii_lowercase, range(1, 27))) | dict(zip(chars, vals))
answer = dp = 0
for c in s:
dp = max(dp, 0) + dct[c]
answer = max(answer, dp)
return answer