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

思路：dp

这道题是不是很像最大子数组和那道题呢?从这里我们其实能看出来一类题的蹊跷规律来：

也就是说，在涉及到子字符串，子数组这样的字眼的时候，并且有最值问题，我们可以基本上确定是动态规划，其次，这类动态规划我们可以设dp数组为以....为尾的含义。

子序列等不连续的也可以这样设dp数组，只不过会多一维循环。

这道题的子数组那道题一样，只不过这里需要做一些改动，那就是我们需要知道这里的价值是多少。题目中给了一部分，其他部分我们也可以自己用循环求。但是这种字符串和数值之间的映射我们应该怎么办？

说到映射，我们一定会想到用一个数据结构，那就是哈希表。OK，这样的话就轻松了。我们直接按照题目要求映射哈希表就行了，然后再对数组进行dp数组转移。

注意：我们最后求出来的结果并不是dp到最后的下标对应的值，而是其中dp数组最大值，因为这里需要求最大子字符串价值，这一点不要忽略，在比较的时候我们的变量要注意从dp[0]开始赋值，然后依次比较，dp[0]我们一开始就直接赋值为一开始所给字符的价值就行了。

上代码：

class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        map<char,int>m;
        char c='a';
        for(int i=1;i<=26;i++){
            m[c++]=i;
        }
        for(int i=0;i<chars.size();i++){
            m[chars[i]]=vals[i];
        }
        vector<int>dp(s.size()+1,0);
        dp[0]=m[s[0]];
        int res=dp[0];
        for(int i=1;i<s.size();i++){
            if(dp[i-1]<=0)
            dp[i]=m[s[i]];
            else
            dp[i]=dp[i-1]+m[s[i]];

            res=max(dp[i],res);
        }
        return res>0?res:0;
    }
};