[经典面试题]最大连续乘积

题目

给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。也就是说，上述数组中，3 0.5 8这3个数的乘积3*0.5*8=12是最大的，而且是连续的。

分析

最大乘积连续子串与最大乘积子序列不同，前者子串要求连续，后者子序列不要求连续。初看此题，自然会想到最大连续乘积问题类似于最大子数组和问题

思路一 穷举法

穷举子串的起点和终点。

代码一

/*---------------------------------------------
*   日期：2015-02-14
*   作者：SJF0115
*   题目: 最大连续乘积
*   来源：
*   博客：
-----------------------------------------------*/
#include <iostream>
#include <cstring>
using namespace std;

class Solution {
public:
    double MaxProduct(double num[],int n){
        if(n <= 0){
            return 0;
        }//if
        double max = num[0];
        double cur;
        int start = 0,end = 0;
        // 起点
        for(int i = 0;i < n;++i){
            cur = 1;
            // 终点
            for(int j = i;j < n;++j){
                cur *= num[j];
                if(cur > max){
                    max = cur;
                    start = i;
                    end = j;
                }//if
            }//for
        }//for
        cout<<"start->"<<start<<" end->"<<end<<endl;
        return max;
    }
};


int main() {
    Solution solution;
    double num[] = {-2.5,4,0,3,0.5,8,-1};
    cout<<solution.MaxProduct(num,7)<<endl;
}

思路二

虽说类似于最大子数组和问题，但实际上有很多细节不同。因为当前最大子数组和只与前一个的最大和有关，但是乘积则不同。乘积会由于负负得正的原因，我们不仅会记录当前最大乘积还要记录当前最小乘积。

代码二

/*---------------------------------------------
*   日期：2015-02-15
*   作者：SJF0115
*   题目: 最大连续乘积
*   来源：
*   博客：
-----------------------------------------------*/
#include <iostream>
#include <cstring>
using namespace std;

class Solution {
public:
    double MaxProduct(double num[],int n){
        if(n <= 0){
            return 0;
        }//if
        double max = num[0];
        double curMax = 1,curMin = 1;
        int maxStart = 0,maxEnd = 0,minStart = 0,minEnd = 0;
        int start = 0,end = 0;
        // 起点
        for(int i = 0;i < n;++i){
            curMax *= num[i];
            curMin *= num[i];
            // 从curMax*num[i] curMin*num[i] num[i]
            // 找到当前最大值和当前最小值
            if(curMax < curMin){
                swap(curMax,curMin);
                maxEnd = i;
                minEnd = i;
                //cout<<"i->"<<i<<endl;
                swap(maxStart,minStart);
                //cout<<"min("<<minStart<<","<<minEnd<<")"<<endl;
                //cout<<"max("<<maxStart<<","<<maxEnd<<")"<<endl;
            }//if
            // 从num[i]重新开始
            // 更新当前最大值
            if(curMax < num[i]){
                curMax = num[i];
                maxStart = i;
            }//if
            maxEnd = i;

            // 更新当前最小值
            if(curMin > num[i]){
                curMin = num[i];
                minStart = i;
            }//if
            minEnd = i;

            if(curMax > max){
                max = curMax;
                start = maxStart;
                end = maxEnd;
            }//if
        }//for
        cout<<"最大连续乘积区间("<<start<<","<<end<<")"<<endl;
        return max;
    }
};


int main() {
    Solution solution;
    double num[] = {-2.5,-4,1,-3,0,8,1};
    cout<<solution.MaxProduct(num,7)<<endl;
}

思路三

这一题目可以用动态规划求解。其实，上述思路本质上也是动态规划，只是解题所表现出来的具体形式跟动态规划不太一样。
假设数组为num[]，考虑到可能存在负数的情况，我们用Max来表示以num[i]结尾的最大连续乘积值，用Min表示以num[i]结尾的最小连续乘积值。
状态转移方程为：

初始状态为Max[0]=Min[0]=num[0]。

代码三

/*---------------------------------------------
*   日期：2015-02-15
*   作者：SJF0115
*   题目: 最大连续乘积
*   来源：
*   博客：
-----------------------------------------------*/
#include <iostream>
#include <cstring>
using namespace std;

class Solution {
public:
    double MaxProduct(double num[],int n){
        if(n <= 0){
            return 0;
        }//if
        double Max[n] ,Min[n],maxVal = num[0];
        Max[0] = Min[0] = num[0];
        for(int i = 1;i < n;++i){
            Max[i] = max(max(num[i],Max[i-1]*num[i]),Min[i-1]*num[i]);
            Min[i] = min(min(num[i],Max[i-1]*num[i]),Min[i-1]*num[i]);
            maxVal = max(maxVal,Max[i]);
        }//for
        return maxVal;
    }
};


int main() {
    Solution solution;
    double num[] = {-2.5,-4,1,3,0,8,5};
    cout<<solution.MaxProduct(num,7)<<endl;
}

相似题目

[经典面试题]子数组的最大乘积