求解最大乘积问题

wuchangjian2021-11-09 17:27:11编程学习

实验目的:

练习贪心

实验内容:

给定一个无序数组,包含正数、负数和0,要求从中找出3个数的乘积,使得乘积最大,并且时间复杂度为O(n)、空间复杂度为O(1)。
输入描述:无序整数数组a[n]。
输出描述:满足条件的最大乘积。
输入样例:
4
3 4 1 2
样例输出:
24

思路:如果数组个数为3,直接返回三者乘积;

如果个数大于三,因为时间复杂度要求O(n),所以只能遍历一遍,记录更新最大的三个数和最小的两个数,这样空间复杂度为O(1),答案是max(最大的三个数之积,最大的数和两个最小的数之积)。注:最小的两个如果是负数,则相乘为正数,可能为最大乘积。

代码

#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

int getmax(vector<int> p) {
    int a1=0,a2=0,a3=0,b1=0,b2=0;
    int n = p.size();
    for (int i = 0; i < n; i++) {
        if (p[i] >= a1) {
            a3 = a2;
            a2 = a1;
            a1 = p[i];
        }
        else if (p[i] >= a2) {
            a3 = a2;
            a2 = p[i];
        }
        else if (p[i] >= a3) {
            a3 = p[i];
        }
        else if (p[i] <= b1) {
            b2 = b1;
            b1 = p[i];
        }
        else if (p[i] <= b2) {
            b2 = p[i];
        }
    }
    return max(a1 * a2 * a3, a1 * b1 * b2);
}

int main()
{
    int n;
    cin >> n;
    vector<int> p(n);
    int ans;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    if (n == 3) ans = p[0] * p[1] * p[2];
    else ans = getmax(p);
    cout << ans;
}

结果截图:

在这里插入图片描述

总结:

一次遍历,记录更新最大的三个和最小的两个

相关文章

idea使用教程-安装和破解

【1】将安装包进行解压--》选择固态盘符 【2】发送到桌面快捷方式,生成一...

线性代数1(2021.10.27)

1.置换矩阵[一个m*n(m<=n)的(0,1)矩阵P为置换矩阵的充要条件...

【前端系列教程之CSS3】02_CSS基础选择器和基础常用样式

【前端系列教程之CSS3】02_CSS基础选择器和基础常用样式

CSS3从入门到精通视频直通车:         CSS3从入门到精通&...

用java判断素数

本解题思路来源于一个小姐姐的博客(应该是个小姐姐)。 素数...

“21 天好习惯”第一期-21

“21 天好习惯”第一期-21

 一:不使用函数 #include<stdio.h>...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。