首页 > 试题广场 >

编程题2

[编程题]编程题2
  • 热度指数：11052 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解

给定一个数组序列, 需要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：

区间中的最小数 * 区间所有数的和最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列  [6 2 1]则根据上述公式, 可得到所有可以选定各个区间的计算值:

 

[6] = 6 * 6 = 36;

[2] = 2 * 2 = 4;

[1] = 1 * 1 = 1;

[6,2] = 2 * 8 = 16;

[2,1] = 1 * 3 = 3;

[6, 2, 1] = 1 * 9 = 9;

 

从上述计算可见选定区间 [6] ，计算值为 36， 则程序输出为 36。

区间内的所有数字都在[0, 100]的范围内;


输入描述:
第一行输入数组序列长度n，第二行输入数组序列。
对于 50%的数据,  1 <= n <= 10000;
对于 100%的数据, 1 <= n <= 500000;


输出描述:
输出数组经过计算后的最大值。
示例1

输入

3
6 2 1

输出

36
算法知识视频讲解
开通博客
头像 已注销
发表于 2021-12-16 23:31:20
考点:前缀和 和 单调栈 举例：[6,2,1,3] 选择第一个数 6，以 6 为最小值的区间是 [6], 结果是 6 * 6 = 36 选择第二个数 2，以 2 为最小值的区间是 [6，2], 结果是 ( 6 + 2 ) * 2 = 24 选择第三个数 1，以 1 为最小值的区间是 [6, 2, 1 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 17c89
发表于 2023-12-17 17:58:56
import java.util.ArrayDeque; import java.util.Arrays; import java.util.Deque; import java.util.HashMap; import java.util.Map; import java.util.Scanner 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 wywzxxz
发表于 2021-01-23 14:27:44
同志们想复杂了，用的方法既满又难写，实际上解法还是很简单的。注意这道题有一个限制：数字都在[0, 100]的范围内，这其实可以拆解为两点：1.值非负，这决定了我们的算法2.值小与100，这省了我们很多事，对笔试非常友好。 注意看目标函数：区间中的最小数 * 区间所有数一个非常自然的想法是我们从小到大 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 我才不是游客
发表于 2021-04-28 19:45:56
单调栈的模板题如果你做过leetcode的柱状图中最大的矩形。枚举元素ai为区间最小值，显然区间越大越好，因此对ai向左右分别找到第一个小于ai的值，此区间即为选择ai为最小值时最大值。枚举a1...an，题目可解。#include <bits/stdc++.h>#define maxn 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 数组 分治 栈 测试开发工程师 测试工程师 2018 字节跳动
上传者：小小
难度：
55条回答 25668浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号