[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有关，那么可以用局部变量即可搞定，而不用使用数组。

http://www.nowcoder.com/profile/864393/test/231563/24590

class Solution {

    public:

        double maxProduct(vector<double> arr) {

            if(arr.size() == )

                return ;

            double minVal = arr[];

            double maxVal = arr[];

            double rtn = arr[];

            double tmpMax = ;

            double tmpMin = ;

            for(int i = ; 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;

        }

};

巴特西

[nowCoder] 子数组最大乘积

最新文章

热门文章