题目描述：

方法1：动态规划，题目类似于最大子数组和，本题中p表示以nums[i]结尾的最大开销的子数组，val哈希表存储每个字母的开销

m是最大开销的子数组

class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        unordered_map<char,int>val;
        for(int i=0;i<chars.length();i++){
            val[chars[i]] = vals[i];
        }
        int p = int(s[0] - 'a') + 1;
        if(val.find(s[0]) != val.end()) p = val[s[0]];
        int m = max(0,p);

        for(int i=1;i<s.length();i++){
            if(val.find(s[i]) != val.end())p = max(p+val[s[i]],val[s[i]]);
            else p = max(p+int(s[i] - 'a')+1,int(s[i] - 'a')+1);
            m = max(m,p);
        }
        return m;
    }
};

优化：，val哈希表可以存储所有字母的价值，上个做法只存储了chars字符串中每个字母的价值，从而导致了多余的if判断

class Solution {
public:
    int maximumCostSubstring(string s, string chars, vector<int>& vals) {
        unordered_map<char,int>val;
        for(char a='a';a<='z';a++){
            val[a] = int(a-'a')+1;
        }
        for(int i=0;i<chars.length();i++){
            val[chars[i]] = vals[i];
        }
        int p = val[s[0]];
        int m = max(0,p);

        for(int i=1;i<s.length();i++){
            p = max(p+val[s[i]],val[s[i]]);
            m = max(m,p);
        }
        return m;
    }
};