最大乘积

2024-01-06 23:23| 来源: 网络整理| 查看: 265

题目描述

给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)

输入描述: 输入共2行，第一行包括一个整数n，表示数组长度第二行为n个以空格隔开的整数，分别为A1,A2, … ,An 输出描述: 满足条件的最大乘积

示例1

输入

复制

4 3 4 1 2 输出

复制

解题思路：我们首先看一下题目，要求的是时间复杂度为o(n)，空间复杂度为o(1)（哦？我写题的时候没考虑这个，所以用的数组存储，那空间复杂度应该也是o(n)了，大家如果要满足这两个条件的话，自己改一下下面代码里的数组，改成任意一个变量就行了）,所以这个题目当然不能三层循环暴力解了。

刚开始我想着从头遍历，相邻的四个数乘起来，再除以最小的那个，这样就能得到最大的乘积，后来发现有特殊情况：

1）如果四个数里最小的是0，那么乘积为0，除0也会报错

2）如果序列中有偶数个不相邻的很小的负数，得到的结果也会错误

所以我改变了思路：

既然只是求三个数的最大乘积，那么三个数里最多也就两个负数，而且越小越好，每次输入都更新最小的两个数，然后在保存最大的三个数，这样，在输入完成之后就得到了所以数字里最大的三个和最小的两个，相乘起来比较大小就能得到结果了

#include using namespace std; int main(){ int i,n; cin>>n; int a[n]; long long ans=1; int maxa,maxb,maxc; //存放给出序列中的三个最大数 maxa=maxb=maxc=-99999999; //初始化为一个很小的值，遇到比这个值大的可以交换 int mina,minb; //存放序列中最小的两个数 mina=minb=99999999; int temp; //交换媒介 for(i=0;i>a[i]; temp=a[i]; //先存放在媒介中 if(a[i]>maxa){ //使得maxa>maxb>maxc swap(a[i], maxa); } if(a[i]>maxb){ swap(a[i],maxb); } if(a[i]>maxc){ swap(a[i], maxc); } a[i]=temp; //从媒介取出 if(a[i]

【本文地址】

公司简介

联系我们