Interview----最长连续乘积字串

题目描述：

给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。

也就是说，上述数组中，3 0.5 8这3个数的乘积3*0.5*8=12是最大的，而且是连续的。

算法1：

首先，枚举的话，复杂度是 O（N^2)

算法2：O（N）

首先发现这个题与最长连续子数组的和非常类似。

考虑用 D.P. 来求解。

定义 max_vec[i] ----- 以 a[i] 结尾的子数组的最大乘积

min_vec[i] ------ 以 a[i] 结尾的子数组的最小乘积。

为什么要定义 min_vec 呢？？ 稍微讲解。。

现在考虑，如何求解 max_vec[i]？？

它的值有以下两种可能：

1. a[i]

2. a[i] * 【a[i] 前面连续的若干个元素的乘积】；

1> if a[i] >= 0，为了让乘积最大，我们取 a[i] * max_vec[i-1] 即可；

2> if a[i] < 0, 为了让乘积最大，我们希望 【a[i]前面连续个若干个元素的乘积】越小越好，因此取 a[i] * min_vec[i-1]

从上面的分析，已经证明了 问题的最优子结构，所以 D.P. 可行。

代码如下：

/**
 * @file max-multiphy.cc
 * @brief max multiphy of a vector
 * @author shoulinjun@126.com
 * @version 0.1.00
 * @date 2014-03-26
 */

#include 
  
   
#include 
   
     using namespace std; double MaxMultiply(double *a, int n) { double result(a[0]); vector
    
      max_vec(n), min_vec(n); max_vec[0] = a[0]; min_vec[0] = a[0]; for(int i=1; i