[数组]NC106 三个数的最大乘积-简单

目暮deep-breaths lv.1

发布时间：2022-11-26 10:42:50 329

描述

给定一个长度为的无序数组，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

要求时间复杂度：空间复杂度。

数据范围：

示例1

输入：

[3,4,1,2]

返回值：

题解

排序解法

思路：

先将数组排序
判断负数的个数k是否大于等于2

k小于2的时候，最大值为最后三个正数的乘积
否则，最大三个数可能是最后三个正数的乘积，或者最小2个负数与最大一个正数的乘积

注意：

实际上，我们不需要求neg_count，可以直接求乘积，不用管最小的2个数是否为负数。

代码如下：

#include <bits/stdc++.h>

using namespace std;

long long solve(int *A, int ALen)
{
  std::sort(A, A + ALen);
  int neg_count = 0;
  while (A[neg_count] < 0)
  {
    neg_count++;
  }

  if (neg_count < 2)
  {
    return A[ALen - 1] * A[ALen - 2] * A[ALen - 3];
  }

  long long ans = A[0];
  ans *= A[1];

  long long b = A[ALen - 2] * A[ALen - 3];
  return A[ALen - 1] * std::max(ans, b);
}

不排序的解法

思路：

实际上，我们只需要找到最小的2个数，以及最大的3个数，然后根据上面的分析直接比较两种情况下的乘积即可。

代码略~~

文章来源： https://blog.51cto.com/u_6650004/5507698

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。