题目描述

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

输入描述:

无序整数数组A[n]

输出描述:

满足条件的最大乘积

示例1

输入

3 4 1 2

输出

24 我看别人的代码很多都是if else用了很麻烦之后就看到了这个代码 基本思路：用选择排序的思路找到最大的3个数和最小的3个数 时间复杂度O(6n) 最大乘积只有三种情况 1.最大的三个数相乘(全是负数或者全是正数的情况) 2.最小的两个负数再乘以最大的正数 从这两种中取最大的即可 循环加数组尽量简化代码 在这里我再帮大家复习一下选择排序的基本思路： 第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换； 第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换； 以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

因为我们只需要找到最大的3个元素和最小的3个元素，所以i直接取<3其余都和选择排序的思想基本类似 代码如下：

#include
          
           #include
           
            using namespace std; const int maxn = 1e6;long long arr[maxn]; int main(){    int n;    long long maxi[3], mini[3], ans;    cin>>n;    for(int i = 0; i < n; i++) scanf("%lld", &arr[i]);    for(int i = 0; i < 3; i++){        for(int j = i + 1; j < n; j++) if(arr[j] > arr[i]) swap(arr[j], arr[i]);        maxi[i] = arr[i];    }    for(int i = 0; i < 3; i++){        for(int j = i + 1; j < n; j++) if(arr[j] < arr[i]) swap(arr[j], arr[i]);        mini[i] = arr[i];    }    ans = max(maxi[0]*maxi[1]*maxi[2],maxi[0]*mini[0]*mini[1]);    printf("%lld\n", ans);}