LeetCode讲解篇之2606. 找到最大开销的子字符串

题目描述

题解思路

本题可以转换成求字符串s可以转换成一个数组f，数组f中每个元素为字符串s中相同位置字符的开销，本题就可以转换成求数组f的最大子数组和
设数组dp中第i号元素表示以s[i]为结尾的子字符串最大开销
那么dp[i] = max(dp[i - 1], 0) + f[i])
即如果dp[i - 1]为负数时，以s[i]为结尾的最大子串开销为f[i]
即如果dp[i - 1]为正数时，以s[i]为结尾的最大子串开销为以s[i - 1]为结尾的最大字串开销加上f[i]

题解代码

func maximumCostSubstring(s string, chars string, vals []int) int {values := [26]int{}for i := 0; i < 26; i++ {values[i] = i + 1}for i := 0; i < len(vals); i++ {values[chars[i] - 'a'] = vals[i]}n := len(s)a := max(values[s[0] - 'a'], 0)ans := afor i := 1; i < n; i++ {a = max(a, 0) + values[s[i] - 'a']ans = max(ans, a)}return ans
}

题解链接

https://leetcode.cn/problems/find-the-substring-with-maximum-cost/