带你粗略了解c++的最大乘积

目录
  • 今天给大家讲最大乘积这道题目
    • 样例
    • 思路
    • 代码
  • 总结

今天给大家讲最大乘积这道题目

最大乘积

内存限制：256 MiB

时间限制：1000 ms

输入文件：maximum.in

输出文件：maximum.out

题目类型：传统

评测方式：文本比较　　

题目描述

给你 n n n个整数 a 1 , a 2 , a 3 , a 4... a n a1,a2,a3,a4...an a1,a2,a3,a4...an 从中任意挑选出个数字，使得乘积最大，输出乘积最大值。

输入格式

输入有多组测试数据。

第一行为整数 t t t，表示测试数据组数。

每组测试数据第一行为整数 n n n，表示数字的数量。

每组测试数据第二行有 n n n个整数 a 1 , a 2 , . . . . a n a1,a2,....an a1,a2,....an

输出格式

每组测试数据输出只有个整数，表示挑选出个数字的乘积最大值。

样例

样例输入

4

5

-1 -2 -3 -4 -5

6

-1 -2 -3 1 2 -1

6

-1 0 0 0 -1 -1

6

-9 -7 -5 -3 -2 1

样例输出

-120

12

0

945

思路

这个题目其实不难。我们先分析一下这个题目。

这个题目要我们从一组数据中 选取五个数 使得这五个数乘积最大。

简单一想 这个不很简单 我们直接从中选取五个最大的数字 然后将这五个数的成乘积直接输出不就完了吗。 但是 仔细一想又发现 不对。刚刚只局限于正数的情况 可是这里还有负数呢! 所以 我们要对这选出来的五个数分情况讨论。

我们要让乘积最大 那么选出来的五个数的乘积 都尽量应该是正数 所以 我们如果要选择负数 那么也最好让它成双成对的出现 因为负负得正 并且这个负数越小乘积就越大。根据此推断 我们将这五个数分为以下几种情况。

一：0个负数 5个正数。即选出这个数列里最大的五个数。

二：2个负数 3个正数。即选出这个数列里最大的三个数和最小的两个数。

三：4个负数 1个正数。即选出这个数列里最大的一个数和最小的四个数。

然后我们将这三种情况算出来的乘积取一个最大值即可。

但是这样就完了吗？ 不你想多了。因为如果这 n n n个数全是负数怎么办？

很简单 我们为了让乘积最大 我们将会选取最大的五个负数。但当我们再回头看一下 发现这不就是第一种情况吗？

所以 我们就不需要特判这种情况了。

代码

#include<bits/stdc++.h>
using namespace std;
long long a[100005];
int n;
int t;
int main()
{
	freopen("maximum.in","r",stdin);
	freopen("maximum.out","w",stdout);
	//文件名输入输出
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;++i)
		cin>>a[i];
		//输入
		sort(a+1,a+n+1);// 给这个数组排序
		cout<<max(a[n]*a[n-1]*a[n-2]*a[n-3]*a[n-4],max(a[n]*a[n-1]*a[n-2]*a[1]*a[2],a[n]*a[1]*a[2]*a[3]*a[4]))<<endl;//按照思路中所讲的三种情况进行取最大值 并记得换行
	}
	return 0;//返回 0
}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

赞 (0)

相关推荐

  • C++实现大数相乘的算法

    由于数字无法用一个整形变量存储,很自然的想到用字符串来表示一串数字.然后按照乘法的运算规则,用一个乘数的每一位乘以另一个乘数,然后将所有中间结果按正确位置相加得到最终结果.可以分析得出如果乘数为A和B,A的位数为m,B的位数为n,则乘积结果为m+n-1位(最高位无进位)或m+n位(最高位有进位).因此可以分配一个m+n的辅存来存储最终结果.为了节约空间,所有的中间结果直接在m+n的辅存上进行累加. C++实现大数相乘代码如下: #include<iostream> #include<st

  • C++实现LeetCode(43.字符串相乘)

    [LeetCode] 43. Multiply Strings 字符串相乘 Given two non-negative integers num1 and num2represented as strings, return the product of num1 and num2, also represented as a string. Example 1: Input: num1 = "2", num2 = "3" Output: "6"

  • C++实现大数相乘算法

    C++实现大数相乘算法

    本文实例为大家分享了C++实现大数相乘的具体代码,供大家参考,具体内容如下 首先说一下乘法计算的算法:同样是模拟人工计算时的方法. 从低位向高位乘,在竖式计算中,我们是将乘数第一位与被乘数的每一位相乘,记录结果之后,用第二位相乘,记录结果并且左移一位,以此类推,直到计算完最后一位,再将各项结果相加,得出最后结果. 计算的过程基本上和小学生列竖式做乘法相同.为编程方便,并不急于处理进位,而将进位问题留待最后统一处理. 我们以125*53为例来说明计算过程: 1.先算125*3,3*5得到15个1,

  • C++自定义API函数实现大数相乘算法

    前言: 之所以取题目的前部分为自定义API函数(不断更新中),是因为笔者想形成一套算法良好.接口清晰.方便编写程序的算法之意,也是为了日后更好调用算法,遇到相似的问题直接调用即可,以及方便大家使用,开发出更高效率的程序.其中的效率不敢说最好,还希望大家互相交流,共同进步!下面进入正题. 普通的乘法计算用int.long.double都可以解决,但有时候需要处理的数字过大,从而产生溢出,以下是实现任意长度的正整数A*B的算法,即大数相乘,这个算法比较简单易懂,思路如下: 1.在主函数用char型数

  • C++实现LeetCode(152.求最大子数组乘积)

    [LeetCode] 152. Maximum Product Subarray 求最大子数组乘积 Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product. Example 1: Input: [2,3,-2,4] Output: 6 Explanation: [2,3] has

  • 带你粗略了解c++的最大乘积

    目录 今天给大家讲最大乘积这道题目 样例 思路 代码 总结 今天给大家讲最大乘积这道题目 最大乘积 内存限制:256 MiB 时间限制:1000 ms 输入文件:maximum.in 输出文件:maximum.out 题目类型:传统 评测方式:文本比较 题目描述 给你 n n n个整数 a 1 , a 2 , a 3 , a 4... a n a1,a2,a3,a4...an a1,a2,a3,a4...an 从中任意挑选出个数字,使得乘积最大,输出乘积最大值. 输入格式 输入有多组测试数据.

  • 带你粗略了解Java数组的使用

    带你粗略了解Java数组的使用

    目录 数组的定义 注意: 数组的创建及初始化: 1.数组的创建: 2.数组的初始化 ①动态初始化: ②静态初始化: 注意事项: 数组的使用 1.数组的长度: 2.数组的访问: 3.数组的遍历: 4.使用数组交换两个整数 5.以字符串的形式输出数组: 理解引用类型: 1.基本类型变量与引用类型变量的区别 2.认识null 3.数组作为方法的返回值 二维数组: 1.创建二维数组及初始化: 2.二维数组长度: 3.二维数组的打印: 4.不规则的二维数组: Array类: 总结 数组的定义 数组:可以看

  • 带你粗略了解C++回文链表

    带你粗略了解C++回文链表

    目录 请判断一个链表是否为回文链表. 思路 总结 请判断一个链表是否为回文链表. 示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->2->1 输出: true 思路 1.用快慢指针,快指针有两步,慢指针走一步,快指针遇到终止位置时,慢指针就在链表中间位置 2.同时用pre记录慢指针指向节点的前一个节点,用来分割链表 3.将链表分为前后均等两部分,如果链表长度是奇数,那么后半部分多一个节点 4.将后半部分反转 ,得cur2,前半部分为cur1 5.按照

  • 带你粗略了解C++流的读写文件

    带你粗略了解C++流的读写文件

    目录 读写文本文件 二进制读写文件 按指定格式读写文件 总结 读写文本文件 C++的IO流: IO:向设备输入数据和输出数据 设备有: 1)文件 2)控制台 3)特定的数据类型(stringstream) C++中,必须通过特定的已经定义好的类, 来处理IO(输入输出) C++的 IO类库为: 文件流:对文件进行读写操作 头文件: < fstream > ifstream 对文件输入(读文件) ofstream 对文件输出(写文件) fstream 对文件输入或输出 文件的打开方式: 模式标志

  • 手把手带你粗略了解Java--类和对象

    手把手带你粗略了解Java--类和对象

    目录 认识类和对象 1.类.对象是什么? 2.什么是面向对象? 3.一个对象的产生过程是?

  • 带你粗略了解C++中的深浅拷贝

    带你粗略了解C++中的深浅拷贝

    目录 一. 背景 二. 代码实现 三. 问题 四. 解决方法 总结 一. 背景 首先看这样一个问题,在Car类中聚合了Engine类 二. 代码实现 下面给出类Car与类Engine的定义 Car.h #ifndef COPY__CAR_H_ #define COPY__CAR_H_ #include "Engine.h" #include <string> using namespace std; class Car { public: // 构造函数 Car(); Ca

  • 初识python的numpy模块

    目录 一.array类型 1.1array类型的基本使用 1.2对更高维度数据的处理 1.3Numpy创建特殊类型的array类型 1.3.1生成全为0或全为1的array 1.3.2np.arrange()和np.linspace() 1.4Numpy基础计算演示 二.线性代数相关 三.矩阵的高级函数-随机数矩阵 四.总结 Numpy是Numerical Python extensions的缩写,字面意思是Python数值计算扩展.Numpy是python中众多机器学习库的依赖,这些库通过Nu

  • AndroidSDK Support自带夜间、日间模式切换详解

    AndroidSDK Support自带夜间、日间模式切换详解

    写这篇博客的目的就是教大家利用AndroidSDK自带的support lib来实现APP日间/夜间模式的切换,最近看到好多帖子在做关于这个日夜间模式切换的开源项目,其实AndroidSDK Support中已经有了非常好的支持了. 本文demo下载地址在文章的末尾,看完文档如果还不能实现可以下载玩玩. -------------------------------------------------------------------------------- 效果演示 左是Android 4

  • C 标准I/O库的粗略实现教程

    写一下fopen/getc/putc等C库的粗略实现,参考了K&R,但是有几点根据自己理解的小改动,下面再具体说一下^_^ 写这篇文章主要是帮助自己理解下标准I/O库大体是怎么工作的. fopen与open之间的关系 操作系统提供的接口即为系统调用.而C语言为了让用户更加方便的编程,自己封装了一些函数,组成了C库.而且不同的操作系统对同一个功能提供的系统调用可能不同,在不同的操作系统上C库对用户屏蔽了这些不同,所谓一次编译处处运行.这里open为系统调用,fopen为C库提供的调用. C库对的读

  • python函数装饰器之带参数的函数和带参数的装饰器用法示例

    本文实例讲述了python函数装饰器之带参数的函数和带参数的装饰器用法.分享给大家供大家参考,具体如下: 1. 函数带多个参数 # 普通的装饰器, 打印函数的运行时间 def decrator(func): def wrap(*args, **kwargs): start_time = time.time() res = func(*args, **kwargs) end_time = time.time() print('运行时间为', end_time-start_time) return

随机推荐