题目
给一个浮点数序列,取最大乘积连续子串的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积连续子串为3,0.5,8。也就是说,上述数组中,3 0.5 8这3个数的乘积3*0.5*8=12是最大的,而且是连续的。
分析
最大乘积连续子串与最大乘积子序列不同,前者子串要求连续,后者子序列不要求连续。初看此题,自然会想到最大连续乘积问题类似于最大子数组和问题
思路一 穷举法
穷举子串的起点和终点。
代码一
#include <iostream>
#include <cstring>
using namespace std;
class Solution {
public:
double MaxProduct(double num[],int n){
if(n <= 0){
return 0;
}
double max = num[0];
double cur;
int start = 0,end = 0;
for(int i = 0;i < n;++i){
cur = 1;
for(int j = i;j < n;++j){
cur *= num[j];
if(cur > max){
max = cur;
start = i;
end = j;
}
}
}
cout<<"start->"<<start<<" end->"<<end<<endl;
return max;
}
};
int main() {
Solution solution;
double num[] = {-2.5,4,0,3,0.5,8,-1};
cout<<solution.MaxProduct(num,7)<<endl;
}
思路二
虽说类似于最大子数组和问题,但实际上有很多细节不同。因为当前最大子数组和只与前一个的最大和有关,但是乘积则不同。乘积会由于负负得正的原因,我们不仅会记录当前最大乘积还要记录当前最小乘积。
代码二
#include <iostream>
#include <cstring>
using namespace std;
class Solution {
public:
double MaxProduct(double num[],int n){
if(n <= 0){
return 0;
}
double max = num[0];
double curMax = 1,curMin = 1;
int maxStart = 0,maxEnd = 0,minStart = 0,minEnd = 0;
int start = 0,end = 0;
for(int i = 0;i < n;++i){
curMax *= num[i];
curMin *= num[i];
if(curMax < curMin){
swap(curMax,curMin);
maxEnd = i;
minEnd = i;
swap(maxStart,minStart);
}
if(curMax < num[i]){
curMax = num[i];
maxStart = i;
}
maxEnd = i;
if(curMin > num[i]){
curMin = num[i];
minStart = i;
}
minEnd = i;
if(curMax > max){
max = curMax;
start = maxStart;
end = maxEnd;
}
}
cout<<"最大连续乘积区间("<<start<<","<<end<<")"<<endl;
return max;
}
};
int main() {
Solution solution;
double num[] = {-2.5,-4,1,-3,0,8,1};
cout<<solution.MaxProduct(num,7)<<endl;
}
思路三
这一题目可以用动态规划求解。其实,上述思路本质上也是动态规划,只是解题所表现出来的具体形式跟动态规划不太一样。
假设数组为num[],考虑到可能存在负数的情况,我们用Max来表示以num[i]结尾的最大连续乘积值,用Min表示以num[i]结尾的最小连续乘积值。
状态转移方程为:
初始状态为Max[0]=Min[0]=num[0]。
代码三
#include <iostream>
#include <cstring>
using namespace std;
class Solution {
public:
double MaxProduct(double num[],int n){
if(n <= 0){
return 0;
}
double Max[n] ,Min[n],maxVal = num[0];
Max[0] = Min[0] = num[0];
for(int i = 1;i < n;++i){
Max[i] = max(max(num[i],Max[i-1]*num[i]),Min[i-1]*num[i]);
Min[i] = min(min(num[i],Max[i-1]*num[i]),Min[i-1]*num[i]);
maxVal = max(maxVal,Max[i]);
}
return maxVal;
}
};
int main() {
Solution solution;
double num[] = {-2.5,-4,1,3,0,8,5};
cout<<solution.MaxProduct(num,7)<<endl;
}
相似题目
[经典面试题]子数组的最大乘积
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
最大K乘积问题: 设I是一个n位十进制整数。如果将I划分为k段,则可得到k个整数。这k个整数的乘积称为I的一个k乘积。试设计一个算法,对于给定的I和k,求出I的最大k乘积。 编程任务: 对于给定的I 和k,编程计算I ...
java基础面试题构建乘积数组本资源系百度网盘分享地址
算法设计实验-最大k乘积问题 亲自用Dev-C++测试实验结果,没有任何问题!
算法设计与分析-最大K乘积问题的源代码 全部经过调试并且已做过试验运行成功
(1)这m个整数的乘积称为S的一个“m乘积”,对于给定的S和m,求S的最大m乘积。 (2)这m个整数的和称为S的一个“m和”,对于给定的S和m,求S的最小m和。 输入格式 输入:三个整数,第一个n表示S的位数,第二个m表示...
C++实现从input.txt读取k值n值以及数据,计算最大k乘积,并将结果写入文件output.txt,压缩包包含文件readme.txt对代码做了简要介绍,将文件路径修改便可运行,如果想对算法深入了解可查看我的博客:...
面试题66. 构建乘积数组题目链接面试题66. 构建乘积数组题目描述给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B
hutc-乘积最大 参考代码hutc-乘积最大 参考代码hutc-乘积最大 参考代码
实现3-13最大k乘积问题.cpp
将一个整数字符串用*分隔成k段后,将每段数字相乘得到的最大乘机
蓝桥杯c++ 蓝桥杯c++_蓝桥杯竞赛练习之算法提高题最大乘积
乘积最大的拆分.zip
题目描述:给一个浮点数序列,取最大乘积连续子串的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积连续子串为3,0.5,8。也就是说,上述数组中,3 0.5 8这3个数的乘积3*0.5*8=12是最大的,而且是连续的。 ...
acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 最大矩阵乘积 acm/icpc 课件 贪心 递归 图论 ...
javascript javascript_leetcode面试题解动态规划问题之第152题乘积最大子数组_题解
最成功的方法之一是最大间距乘积(MPS)。 但是,通过这种方法对数据进行建模时会遇到一个问题,即当超出范围时,该方法就会失效。 这项研究提供了一种即使在包含关系的情况下也可以对数据建模的解决方案。 在这项...
问题描述:设n是一个正整数,将n分解为若干互不相同的自然数之和,且使这些自然数的乘积最大。 本讲义提供该问题的正确算法的自然语言描述及其严格证明。
给定一个n个元素的数组,数组元素全部为整数,负数,正数和0均有可能存在,设设计一个算法,找出连续的几个数组元素相乘积最大
最大K乘积问题 设I是一个n位十进制整数。如果将I划分为k段,则可得到k个整数。...设w(h,k) 表示: 从第1位到第K位所组成的十进制数,设m(i,j)表示前i位(1-i)分成j段所得的最大乘积,则可得到如下经典的DP方程: if(j==1)
找出数组中连续相乘后能得出最大乘积的一组数字,算法十分精妙