动态规划题目（三）——最大连续乘积子串

绝地灬酷狼 2022-08-06 01:27 284阅读 0赞

**动态规划题目（三）——最大连续乘积子串**

# 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; 
    }