当前位置：首页 > article >正文

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

article 2025/1/22 20:59:42

文章目录

题目描述
题解思路
题解代码
题解链接

题目描述

在这里插入图片描述

题解思路

本题可以转换成求字符串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 := a
    for i := 1; i < n; i++ {
        a = max(a, 0) + values[s[i] - 'a']
        ans = max(ans, a)
    }

    return ans
}