JZTXT

2606 找到最大开销的子字符串

发布时间 2023-04-09 01:14:01作者: lxy_cn

题目链接：2606. 找到最大开销的子字符串

方法：动态规划

解题思路

实际是：子数组最大和

  • 初始化每个字母的价值，保存在vector<int> value(26)中；
  • 设\(dp[i]\)表示以\(s[i]\)结尾的子字符串的最大开销，那么就可以使得dp[i + 1]和dp[i]联系起来，有两种情况：
    • 将\(s[i + 1]\)接到上一个子字符串的后面，dp[i - 1] + value[s[i+1] - 'a']；
    • 选择\(s[i + 1]\)为子字符串的起点，value[s[i+1] - 'a']。
  • 取其中最大开销：\(dp[i + 1] = max(情况1, 情况2)\)；
  • 然后答案就是所有以\(s[i]\)结尾的子字符串最大开销中的最大值。
  • 优化\(dp\)数组为\(O(1)\)，有上述的计算过程可知，当前的\(dp\)值只和上一个\(dp\)值有关，那么只需要用一个\(dp\)变量就可以。

代码

class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        vector<int> value(26);
        for (int i = 0; i < 26; i ++ ) value[i] = i + 1;
        for (int i = 0; i < chars.length(); i ++ ) value[chars[i] - 'a'] = vals[i];
        int dp = 0, ans = 0;
        for (auto &c : s) {
            dp = max(dp + value[c - 'a'], value[c - 'a']);
            ans = max(ans, dp);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。