首页 > 代码库 > 编程之美 子数组最大乘积
编程之美 子数组最大乘积
给定一个长度为N的整数数组,只允许用乘法不允许用除法,计算N-1个数组合的乘积最大的一组,并写出算法的时间复杂度。
去除第i个元素的乘积可以表示为A[0]*A[1]*…A[i-1] * A[i+1]*A[i+2]*…A[N-1]
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1003
long long A[MAXN];
long long s[MAXN];
long long t[MAXN];
int main()
{
int n, i;
cin >> n;
for (i=1; i<=n; i++)
cin >> A[i];
// 从前往后用叠乘法
s[0] = 1;
for (i=1; i<n; i++)
s[i]=A[i]*s[i-1];
// 从后往前用叠乘法
t[n+1] = 1;
for (i=n; i>1; i--)
t[i]=A[i]*t[i+1];
// 计算出n-1个n-1数连乘
for (i=0; i<=n-1; i++)
s[i] = s[i]*t[i+2];
long long maximum = s[0];
// 获取其中的最大值
for (i=1; i<=n-1; i++)
maximum = max(maximum, s[i]);
cout << maximum << endl;
}
编程之美 子数组最大乘积
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。