给定一个double类型的数组arr，其中的元素可正、可负、可0，返回子数组累乘的最大乘积。例如，arr=[-2.5, 4, 0, 3, 0.5, 8, -1]，子数组[3, 0.5, 8]累乘可以获得最大的乘积12，所以返回12
[要求]
时间复杂度为)
，空间复杂度为)
[编程题]数组中子数组的最大累乘积
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
double a[n], Max=1, Min=1, s=0;
for(int i=0;i<n;i++){
cin>>a[i];
double s1 = Max * a[i];
double s2 = Min * a[i];
Max = max(a[i], max(s1, s2));
Min = min(a[i], min(s1, s2));
s = max(s, Max);
}
printf("%.2f\n", s);
return 0;
}
发表于 2020-02-23 01:23:26
回复(0)
用动态规划求解，思路跟求数组最大连续累乘值相同。在遍历数组的过程中，比较当前数是累乘在之前的结果上能更大，还是从当前的数重新开始乘会更大。但在遇到负数时，要将之前累乘策略中的最大和最小值交换，因为符号反转能使得数值大小两极反转。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] strArr = br.readLine().split(" ");
double[] nums = new double[n];
for(int i = 0; i < n; i++) nums[i] = Double.parseDouble(strArr[i]);
double dmax = 1.0, dmin = 1.0;
double max = Double.MIN_VALUE;
for(int i = 0; i < n; i++){
if(nums[i] < 0){
// 遇到负数时，需要交换一下到目前为止的最大累乘值和最小累乘值，因为会使得最大的变最小，最小的变最大
double temp = dmax;
dmax = dmin;
dmin = temp;
}
dmax = Math.max(dmax * nums[i], nums[i]);
dmin = Math.min(dmin * nums[i], nums[i]);
max = Math.max(max, dmax);
}
System.out.println(String.format("%.2f", max));
}
}
发表于 2021-11-17 14:57:20
回复(0)
首先，这题比较坑的地方就是最后要输出两位小数，可以用String.format("%.2f",res)来保留两位小数，否则默认一位。
思路就是从左到右扫描，假设i位置是子数组的最后一个数，看以这个数结尾最大的乘积是多少，是一个一维的动态规划，当然，压缩一下空间，用两个变量就可以遍历了。
因为有负数，所以还要保留一下每一次循环最小的值，也许下一次遇上一个负数之后，负负得正，变成了最大值了
//本题可以直接上动态规划，假设i位置是一个子数组的最后一位，它的最大乘积是多少,
//由于包含负数，所以最小的也要查看一下,并在每一次循环，看看这个负数有没有晋升（变成最大正数）的机会
import java.util.*;
public class Main {
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
int n;
while(cin.hasNext())
{
n = cin.nextInt();
double[] a=new double[n];
for(int i=0;i<n;i++){
a[i]=cin.nextDouble();
}
process_getMaxMulti(a);
}
}
public static void process_getMaxMulti(double[] a){
double max=a[0];
double min=a[0];
double res=max;
for(int i=1;i<a.length;i++){
//源代码的错误是，用改了之后的max值来更新min
double maxEnd=max*a[i];
double minEnd=min*a[i];
max=Math.max(Math.max(maxEnd,a[i]),minEnd);
min=Math.min(Math.min(minEnd,a[i]),maxEnd);
res=Math.max(res,max);
}
System.out.println(String.format("%.2f", res));
}
}
//由于包含负数，所以最小的也要查看一下,并在每一次循环，看看这个负数有没有晋升（变成最大正数）的机会
import java.util.*;
public class Main {
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
int n;
while(cin.hasNext())
{
n = cin.nextInt();
double[] a=new double[n];
for(int i=0;i<n;i++){
a[i]=cin.nextDouble();
}
process_getMaxMulti(a);
}
}
public static void process_getMaxMulti(double[] a){
double max=a[0];
double min=a[0];
double res=max;
for(int i=1;i<a.length;i++){
//源代码的错误是，用改了之后的max值来更新min
double maxEnd=max*a[i];
double minEnd=min*a[i];
max=Math.max(Math.max(maxEnd,a[i]),minEnd);
min=Math.min(Math.min(minEnd,a[i]),maxEnd);
res=Math.max(res,max);
}
System.out.println(String.format("%.2f", res));
}
}
发表于 2020-08-11 16:13:22
回复(0)
累乘不同于累加(当sum <=0 即可舍弃), 这里需要考虑负负得正的情况
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
double num; scanf("%d%lf", &n,&num);
double maxX = num;
double minX = num;
double ans = num;
for(int i=1; i<n; i++){
scanf("%lf", &num);
double temp = maxX;
maxX = max(max(num*maxX, num*minX), num);
minX = min(min(num*temp, num*minX), num);
ans = max(ans, maxX);
}
printf("%.2f", ans);
return 0;
}
编辑于 2020-02-15 00:11:47
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
double[] arr = new double[n];
for(int i=0;i<n;i++){
arr[i] = scanner.nextDouble();
}
double max = 1,min = 1,res = Integer.MIN_VALUE,p=0,q=0;
for(int i=0;i<n;i++) {
p = max * arr[i];
q = min * arr[i];
max = Math.max(Math.max(p, q), arr[i]);
min = Math.min(Math.min(p, q), arr[i]);
res = Math.max(res, max);
}
System.out.print(String.format("%.2f", res));
}
}
发表于 2019-10-24 16:57:45
回复(0)
#include<iostream>
#include<vector>
#include<algorithm>
#include <iomanip>
using namespace std;
int main() {
int N;
vector<double> arrIn;
cin >> N;
for (int i = 0; i<N; i++) {
double temp;
cin >> temp;
arrIn.push_back(temp);
}
double res = arrIn[0];
double maxc = arrIn[0];
double minc = arrIn[0];
double premax = 0, premin = 0;
/*计算以i结尾子数组最大乘积
1,以arr[i-1]结尾的最大乘积premax*arr[i];
2,以arr[i-1]结尾的最小乘积premin*arr[i]; 两个负数相乘
3,本身arr[i]最大
*/
for (int i = 1; i < N; i++) {
premax = maxc*arrIn[i];
premin = minc*arrIn[i];
maxc = max(max(premax, premin), arrIn[i]);
minc = min(min(premax, premin), arrIn[i]);
res = max(res, maxc);
}
cout << fixed << setprecision(2) << res << endl;
return 0;
}
发表于 2019-09-04 21:59:06
回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
vector<double>num(n);
for(int i=0;i<n;i++)
cin>>num[i];
double res=num[0],minn = num[0],maxx = num[0];
for(int i=1;i<n;i++)
{
double x = maxx;
maxx = max(num[i],max(minn*num[i], maxx*num[i]));
minn = min(num[i], min(minn*num[i], x*num[i]));
res = max(res, maxx);
}
cout<<fixed << setprecision(2) <<res<<endl;
return 0;
}
发表于 2019-08-28 21:07:13
回复(0)
# include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<double> nums(n);
for(int i = 0; i < n; ++i) cin >> nums[i];
double ans = 0;
// 一个保存最大的，一个保存最小的。
double maxsum = 1;
double minsum = 1;
for(int i = 0; i < n; ++i){
// 如果遇到数组的数是负数，那么会导致最大的变最小的，最小的变最大的。因此交换两个的值
if(nums[i] < 0) swap(maxsum, minsum);
// 数组元素为正数的情况，最大乘积可能是乘上当前元素，也可能变成元素本身
// 取决于上一个元素为止的最大乘积是正数还是负数
maxsum = max(nums[i], maxsum * nums[i]);
// 维护一个最小乘积，在元素 < 0 时使用
minsum = min(nums[i], minsum * nums[i]);
ans = ans > maxsum ? ans : maxsum;
}
printf("%.2f\n", ans);
return 0;
}
发表于 2022-04-11 13:12:39
回复(0)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
int n = 0;
cin >> n;
vector<double> arr(n, 0);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
if (n == 0) {
printf("%.2f", 0.00);
return 0;
}
double p1 = 0, p2 = 0, p3 = 0;
double maxValue = arr[0], minValue = arr[0], res = arr[0];
for (int i = 1; i < n; i++) {
// 可能值1: 过去的最大连续值 * 当前值
p1 = maxValue * arr[i];
// 可能值2: 过去的最小连续值 * 当前值
p2 = minValue * arr[i];
// 可能值3: 当前值
p3 = arr[i];
// 3个可能值取一个最大值
maxValue = max(max(p1, p2), p3);
minValue = min(min(p1, p2), p3);
res = max(maxValue, res);
}
printf("%.2f", res);
return 0;
}
发表于 2021-12-09 10:05:15
回复(0)
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
double func(const std::vector<double>& vec) {
if (vec.empty()) {
return 1;
}
double sum = 1;
double max = vec[0];
for (int i = 0; i < vec.size(); ++i) {
sum = sum * vec[i];
if (sum < 1 && sum > - 1) {
sum = vec[i];
}
max = std::max(sum, max);
}
return max;
}
int main() {
int n;
std::cin >> n;
std::vector<double> vec(n, 0.0);
for (int i = 0; i < n; ++i) {
std::cin >> vec[i];
}
printf("%.2f\n", func(vec));
#include <algorithm>
#include <vector>
#include <climits>
double func(const std::vector<double>& vec) {
if (vec.empty()) {
return 1;
}
double sum = 1;
double max = vec[0];
for (int i = 0; i < vec.size(); ++i) {
sum = sum * vec[i];
if (sum < 1 && sum > - 1) {
sum = vec[i];
}
max = std::max(sum, max);
}
return max;
}
int main() {
int n;
std::cin >> n;
std::vector<double> vec(n, 0.0);
for (int i = 0; i < n; ++i) {
std::cin >> vec[i];
}
printf("%.2f\n", func(vec));
}
想知道这样的做为啥过不去？：累乘小于1的绝对值的话，就更新累乘积，否则的话就一直累乘，然后对累乘求最大
发表于 2021-07-24 15:38:23
回复(0)
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int t = cin.nextInt();
cin.nextLine();
String[] line = cin.nextLine().split(" ");
double[] nums = new double[t];
for (int i=0; i < t; i++) {
nums[i] = Double.parseDouble(line[i]);
}
double dp_min_i = nums[0];
double dp_max_i = nums[0];
double dp_min_ii = Double.MAX_VALUE;
double dp_max_ii = 0;
double ret = nums[0];
for (int i=1; i < t; i++) {
double tmp_1 = dp_min_i * nums[i];
double tmp_2 = dp_max_i * nums[i];
dp_min_ii = Math.min(tmp_1, Math.min(tmp_2, nums[i]));
dp_max_ii = Math.max(tmp_1, Math.max(tmp_2, nums[i]));
ret = Math.max(dp_max_ii, ret);
dp_min_i = dp_min_ii;
dp_max_i = dp_max_ii;
}
System.out.printf("%.2f\n", ret);
}
}
腾讯PCG实习面试，当成加法做了，面试官为啥不提醒我错了😥
我就觉得有点奇怪，测了一个例子后就不敢懂了
发表于 2021-03-17 15:43:00
回复(0)
#include<iostream>
using namespace std;
const int N = 1e5+10;
double a[N];
inline double max(double a,double b ,double c) {
return max(a,max(b,c));
}
inline double min(double a,double b,double c) {
return min(a,min(b,c));
}
int main() {
int n;
cin>>n;
double res=0;
double t1=1,t2 = 1;
for(int i=0;i<n;++i) {
cin>>a[i];
}
for(int i=0;i<n;++i) {
double s1 = t1*a[i];
double s2 = t2*a[i];
t1 = max(a[i],s1,s2);
t2 = min(a[i],s1,s2);
res = max(res, t1);
}
printf("%.2lf" ,res);
}
发表于 2021-01-31 00:34:58
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-10-11 20:39:00
-
2022-09-12 12:02:22
-
2022-09-11 16:07:06
-
2022-08-27 11:12:33 -
2022-08-22 13:18:53
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
