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

绝地灬酷狼 2022-08-06 01:27 311阅读 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)。

代码如下:

  1. #include<iostream>
  2. #include<algorithm>
  3. #define max(a, b) (((a) > (b)) ? (a) : (b)) //宏定义,注意加括号
  4. #define min(a, b) (((a) < (b)) ? (a) : (b))
  5. using namespace std;
  6. double findMaxProduct(double *a, int num)
  7. {
  8. double maxProduct=a[0];
  9. double maxEnd=a[0]; //记录当前最大值
  10. double minEnd=a[0]; //记录当前最小值,因为后面会出现负数的话,当前的最小值就会逆袭~!
  11. for (int i=1; i<num; i++)
  12. {
  13. maxEnd=max(max(maxEnd*a[i], minEnd*a[i]), a[i]); //更新当前最大值
  14. minEnd=min(min(maxEnd*a[i], minEnd*a[i]), a[i]); //更新当前最小值
  15. maxProduct=max(maxEnd, maxProduct); //乘积最大值一定是二选一
  16. }
  17. return maxProduct;
  18. }
  19. int main()
  20. {
  21. double a[7]={-2.5, 4, 0, 3, 0.5, 8, -1};
  22. int num=7;
  23. double maxProduct=findMaxProduct(a, num);
  24. cout<<maxProduct<<endl;
  25. }

发表评论

表情:
评论列表 (有 0 条评论,311人围观)

还没有评论,来说两句吧...

相关阅读

    相关 连续

    题描述: 给定一个由数字组成的数组,求出和最大的子数组 求解方法: 1.暴力法 选取所有连续和的可能性,O(n^2) 2.分析法 当遍历到第i个元素时,判断在...