719. Calculate Maximum Value

Code(Language:C++)

class Solution {
public:
    /**
     * @param str: the given string
     * @return: the maximum value
     */
    int calcMaxValue(string &str) {
        // write your code here
        ///这个题很有代表性。开始时，想的特别复杂，DFS, 每个位置放 * 还是+，括号放哪里，特别复杂。
        //实际本题就是DP解，每一步有两个action * or +，基于上一步的最大值，在两个action中选当前最大值。
        //解法思想。别老想着DFS，所有可能。
        const int n = str.size();
        if(n == 0){
            return 0; 
        }
        int res = 0;
        for(int i = 0; i < n; i++){
            int v = str[i] - '0';
            res = max(res + v, res * v); 
        }
        return res; 
    }
};