5.1 最大连续乘积子串
最后更新于：2022-04-01 15:00:47
## 题目描述
给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。也就是说，上述数组中，3 0.5 8这3个数的乘积3_0.5_8=12是最大的，而且是连续的。
## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.01.md#分析与解法)分析与解法
此最大乘积连续子串与最大乘积子序列不同，请勿混淆，前者子串要求连续，后者子序列不要求连续。也就是说，最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence，LCS）是：
* 子串（Substring）是串的一个连续的部分，
* 子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；
更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串“ acdfg ”同“ akdfc ”的最长公共子串为“ df ”，而它们的最长公共子序列LCS是“ adf ”，LCS可以使用动态规划法解决。
### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.01.md#解法一)解法一
或许，读者初看此题，可能立马会想到用最简单粗暴的方式：两个for循环直接轮询。
~~~
double maxProductSubstring(double *a, int length)
{
double maxResult = a[0];
for (int i = 0; i < length; i++)
{
double x = 1;
for (int j = i; j < length; j++)
{
x *= a[j];
if (x > maxResult)
{
maxResult = x;
}
}
}
return maxResult;
}
~~~
但这种蛮力的方法的时间复杂度为O(n^2)，能否想办法降低时间复杂度呢？
### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.01.md#解法二)解法二
考虑到乘积子序列中有正有负也还可能有0，我们可以把问题简化成这样：数组中找一个子序列，使得它的乘积最大；同时找一个子序列，使得它的乘积最小（负数的情况）。因为虽然我们只要一个最大积，但由于负数的存在，我们同时找这两个乘积做起来反而方便。也就是说，不但记录最大乘积，也要记录最小乘积。
假设数组为a[]，直接利用动态规划来求解，考虑到可能存在负数的情况，我们用maxend来表示以a[i]结尾的最大连续子串的乘积值，用minend表示以a[i]结尾的最小的子串的乘积值，那么状态转移方程为：
~~~
maxend = max(max(maxend * a[i], minend * a[i]), a[i]);
minend = min(min(maxend * a[i], minend * a[i]), a[i]);
~~~
初始状态为maxend = minend = a[0]。
参考代码如下：
~~~
double MaxProductSubstring(double *a, int length)
{
double maxEnd = a[0];
double minEnd = a[0];
double maxResult = a[0];
for (int i = 1; i < length; ++i)
{
double end1 = maxEnd * a[i], end2 = minEnd * a[i];
maxEnd = max(max(end1, end2), a[i]);
minEnd = min(min(end1, end2), a[i]);
maxResult = max(maxResult, maxEnd);
}
return maxResult;
}
~~~
动态规划求解的方法一个for循环搞定，所以时间复杂度为O(n)。
## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.01.md#举一反三)举一反三
1、给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。
分析：我们可以把所有可能的（N-1）个数的组合找出来，分别计算它们的乘积，并比较大小。由于总共有N个（N-1）个数的组合，总的时间复杂度为O（N2），显然这不是最好的解法。