动态规划题目(三)——最大连续乘积子串
动态规划题目(三)——最大连续乘积子串
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;
}
还没有评论,来说两句吧...