友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
2606. 找到最大开销的子字符串
给你一个字符串 s，一个字符 互不相同 的字符串 chars 和一个长度与 chars 相同的整数数组 vals 。
子字符串的开销 是一个子字符串中所有字符对应价值之和。空字符串的开销是 0 。
字符的价值 定义如下：
-
如果字符不在字符串
chars中，那么它的价值是它在字母表中的位置（下标从 1 开始）。-
比方说，
a的价值为1，b的价值为2，以此类推，z的价值为26。
-
-
否则，如果这个字符在
chars中的位置为i，那么它的价值就是vals[i]。
请你返回字符串 s 的所有子字符串中的最大开销。
示例 1：
输入：s = "adaa", chars = "d", vals = [-1000] 输出：2 解释：字符 "a" 和 "d" 的价值分别为 1 和 -1000 。 最大开销子字符串是 "aa" ，它的开销为 1 + 1 = 2 。 2 是最大开销。
示例 2：
输入：s = "abc", chars = "abc", vals = [-1,-1,-1] 输出：0 解释：字符 "a" ，"b" 和 "c" 的价值分别为 -1 ，-1 和 -1 。 最大开销子字符串是 "" ，它的开销为 0 。 0 是最大开销。
提示：
-
1 <= s.length <= 105 -
s只包含小写英文字母。 -
1 <= chars.length <= 26 -
chars只包含小写英文字母，且 互不相同 。 -
vals.length == chars.length -
-1000 <= vals[i] <= 1000
思路分析
动态规划。利用后两个参数加字母表，可以求出每个字母对应的价值。其余就是一个“最大子数组和”，直接利用 Kadane 算法即可。
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-10-02 22:39:46
*/
public int maximumCostSubstring(String s, String chars, int[] vals) {
int[] values = new int[26];
for (int i = 0; i < values.length; i++) {
values[i] = i + 1;
}
for (int i = 0; i < vals.length; i++) {
char c = chars.charAt(i);
values[c - 'a'] = vals[i];
}
int result = 0;
int[] dp = new int[s.length()];
dp[0] = values[s.charAt(0) - 'a'];
result = Math.max(result, dp[0]);
for (int i = 1; i < s.length(); i++) {
dp[i] = Math.max(0, dp[i - 1]) + values[s.charAt(i) - 'a'];
result = Math.max(result, dp[i]);
}
return result;
}