1. 题目描述

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

2. 动态规划求解

动态规划求解题目的时候最重要的是要找到状态转移方程！

针对这道题目，我们使用两个变量记录当前最大值maxEnd, 和当前最小值minEnd。为什么记录当前最小值呢？因为数组中会出现负数，乘以一个负数的话，当前最小值是会逆袭的！！

然后就是状态转移方程中对这两个变量的更新：

maxEnd=max(max(maxEnd*a[i], minEnd*a[i]), a[i]); //更新当前最大值
minEnd=min(min(maxEnd*a[i], minEnd*a[i]), a[i]); //更新当前最小值

下面的解法时间复杂度为O(n)。

代码如下：

#include<iostream>
#include<algorithm>
#define max(a, b)  (((a) > (b)) ? (a) : (b))  //宏定义，注意加括号
#define min(a, b)  (((a) < (b)) ? (a) : (b))
using namespace std; 
double findMaxProduct(double *a, int num)
{
    double maxProduct=a[0]; 
    double maxEnd=a[0];  //记录当前最大值
    double minEnd=a[0];  //记录当前最小值，因为后面会出现负数的话，当前的最小值就会逆袭~！
    for (int i=1; i<num; i++)
    {
        maxEnd=max(max(maxEnd*a[i], minEnd*a[i]), a[i]);  //更新当前最大值
        minEnd=min(min(maxEnd*a[i], minEnd*a[i]), a[i]);   //更新当前最小值
        maxProduct=max(maxEnd, maxProduct);   //乘积最大值一定是二选一
    }
    return maxProduct; 
}
int main()
{
    double a[7]={-2.5, 4, 0, 3, 0.5, 8, -1}; 
    int num=7; 
    double maxProduct=findMaxProduct(a, num); 
    cout<<maxProduct<<endl; 
}