[nowCoder] 子數組最大乘積

給定一個double類型的數組arr，其中的元素可正可負可0，傳回子數組累乘的最大乘積。例如arr=[-2.5，4，0，3，0.5，8，-1]，子數組[3，0.5，8]累乘可以獲得最大的乘積12，是以傳回12。

分析，是一個dp的題目，

設f[i]表示以i為結尾的最大值，g[i]表示以i結尾的最小值，那麼

f[i+1] = max{f[i]*arr[i+1], g[i]*arr[i+1],arr[i+1]} ,隻有這三種情況。

考慮到f[i]，g[i]隻和i-1有關，那麼可以用局部變量即可搞定，而不用使用數組。

class Solution {
    public:
        double maxProduct(vector<double> arr) {
            if(arr.size() == 0)
                return 0;
            double minVal = arr[0];
            double maxVal = arr[0];
            double rtn = arr[0];
 
            double tmpMax = 0;
            double tmpMin = 0;
 
            for(int i = 1; i < arr.size(); i++)
            {  
                //cout << "max\t" << maxVal << endl;
                //cout << "min\t" << minVal << endl;
                tmpMax = max(maxVal * arr[i], minVal * arr[i]);
                tmpMin = min(maxVal * arr[i], minVal * arr[i]);
 
                maxVal = max(tmpMax, arr[i]);
                minVal = min(tmpMin, arr[i]);
 
                rtn = max(rtn, maxVal);
            }  
            return rtn;
        }  
};