关键词：
题目描述
给定一个数组序列，需要选出一个区间，使得该区间是所有区间中经过如下计算的值最大的一个。
区间中的最小数 * 区间所有数的和
最后程序输出经过计算后的最大值即可，不需要输出具体的区间。如给定序列[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
则程序输出36
区间所有数字都在【0,100】的范围内。
解题思路：
可以看出我们需要维护一个区间，同时我们能知道区间的最小值，和这个区间所有数字的和。
但是，有一点我们可以清楚知道，如果一个区间的最小值已经确定，那么我们就要尽量使得区间的和最大。其实本问题就可以转换到遍历数组，以当前位置为最小值，向左向右>=当前值能扩展的最大距离问题，我们知道这样的方法时间复杂度是O(n^2)。
嗯 区间的最小值和区间边界我们可以用单调栈去维护，这样时间复杂度就降到O(n)
其实大小都有了，输出区间边界也就不难了。我这里 输出了最大值和 区间的开始结束位置。如果有多个区间=max，我输出的是字典序较小的区间，代码如下：
给几个比较有用的数据
1
0
ans:
0
1 1
---------------------
9
1 1 1 1 1 1 1 2 2
ans:
11
1 9
----------------
4
1 3 2 4
ans:
18
2 4
----------------
#include <iostream> #include <stdio.h> #include <vector> using namespace std; typedef long long ll; ll a[100010]; class node { public: ll left, right,x; }; ll sum[100010]; int main() { // 维护一个递增的栈 int n; vector<node> st; while (cin>>n) { ll ans = -1; if (n == 0) { cout << 0 << endl << 0 << " " << 0 << endl;continue; } ll l = 0, r = 0; while (!st.empty()) st.pop_back(); sum[0] = 0; for (int i = 1; i <= n; ++i) { scanf("%lld",&a[i]); sum[i] = sum[i-1] + a[i]; } for (int i = 1; i <= n; ++i) { if (st.empty()) { st.push_back({i,i,a[i]}); } else { node u = st.back(); if (a[i] > u.x) { st.push_back({i,i,a[i]}); } else { int ileft=0,iright=0; while (!st.empty()) { node v = st.back(); if (v.x >= a[i]) { st.pop_back(); ileft = v.left; if(st.size()) st.back().right = v.right; ll tmp = (sum[v.right] - sum[v.left-1])*v.x; if (tmp >= ans) { ans = tmp; l = v.left; r = v.right; } } else break; } st.push_back({ileft,i,a[i]}); } } } while (!st.empty()) { node v = st.back(); st.pop_back(); if(st.size()) st.back().right = v.right; ll tmp = (sum[v.right] - sum[v.left-1])*v.x; if (tmp >= ans){ ans = tmp; l = v.left; r = v.right; } } cout << ans << endl << l << " " << r << endl; } return 0; }
今日头条2018aicamp5月26日在线笔试编程题第一道——最佳路径(代码片段)
题目给定一个n*m的矩阵A，矩阵中每一个元素为一个十六进制数。寻找一条从左上角都右下角的路径，每次只能向右或者向下移动， 使得路径上所有数字之积在16进制下的后缀0最少。输入描述：第一行：n,m(2<=n,m<=1000) ... 查看详情
笔试今日头条-线段树查询
【题目描述】给定两个长度为 n 的整数数列 A 和 B。再给定 q 组查询，每次查询给出两个整数 x 和 y，求满足 Ai>=x 且 Bi>=y 这样的 i 的数量。输入格式第一行给定两... 查看详情
实习生求职今日头条笔试
时间：大三下学期职位：测试开发过程： 首先，会有练习题，但是练习题没有针对性，而且编程题会很简单；主要是用来检查自己的环境是否合适、熟悉系统。 然后就是正式考试了——开始会很卡（反... 查看详情
8.22今日头条笔试
这次套路深啊，怎么还有改错题！。上来看题，每个题目的输入数据都很大，果断上scanf,printf,千万不能用cin,cout1.右上角的点，我的思路是先对每一行去重（题目好像说没有重的点耶！），每一行只有最右边的点才是候选点，然... 查看详情
今日头条2018校招后端方向（第二批）第一题二分查找(代码片段)
原题链接 https://www.nowcoder.com/test/8537209/summary题意n个数 q个查询 L,R,K L到R区间内为K的数有多少个数据范围 n<=300000,q<=300000 解析 对于每次查询必须要O(logn)复杂度才行 所以想到二分查找 因为数... 查看详情
字节跳动（今日头条）的题目真的难吗？
大家好鸭，我是好好学习天天编程的天天，一个每天都努力精进，并努力分享的主儿。今天给聊得话题是关于字节跳动笔试题难度的。在各种交流群了，总是能看到大家在说字节跳动的题目好难呀，4个编程题没有一个题AC。天天... 查看详情
头条笔试题2018后端第二批(代码片段)
...签（空格分隔）：笔试题描述：为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一... 查看详情
美团笔试-第二题最大汉明距离：
题目描述 给出n个数，求这n个数中两两最大的汉明距离，两个数的汉明距离定义维两个二进制表示中不同的位数。 例如11和6的汉明距离为3，因为11转换为二进制后为1011，6转换为二进制后为0110，他们的二进制第1，3，4位... 查看详情
2018今日头条(代码片段)
P为给定的二维平面整数点集。定义P中某点x，如果x满足P中任意点都不在x的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复,坐标轴范围在[0,1e9)内）... 查看详情
今日头条笔试题--2018优先队列(代码片段)
时间限制：1秒空间限制：81920K产品经理(PM)有很多好的idea，而这些idea需要程序员实现。现在有N个PM，在某个时间会想出一个idea，每个idea有提出时间、所需时间和优先等级。对于一个PM来说，最想实现的idea首先考虑优先等级高的... 查看详情
字节跳动（今日头条）的题目真的难吗？
大家好鸭，我是好好学习天天编程的天天，一个每天都努力精进，并努力分享的主儿。今天给聊得话题是关于字节跳动笔试题难度的。在各种交流群了，总是能看到大家在说字节跳动的题目好难呀，4个编程题没有一个题AC。天天... 查看详情
今日头条”杯2018年湖北省赛网）(代码片段)
所有题目： http://cdn.vo-ov.cn/online_f9ec217.pdf F:A-maze-ing哇我也是哭了...dfs写错，dfs还用了vis数组，实际上并不需要，WA了N多次...呜呜呜看出来对图的基本概念还比较生疏，或者说都忘了好多，一开始还在纠结环是不是强连通... 查看详情
美团笔试-第二题最大汉明距离：
题目描述 给出n个数，求这n个数中两两最大的汉明距离，两个数的汉明距离定义维两个二进制表示中不同的位数。 例如11和6的汉明距离为3，因为11转换为二进制后为1011，6转换为二进制后为0110，他们的二进制第1，3，4位... 查看详情
2018今日头条春招的一道笔试题——通过改变枚举的变量进行枚举优化(代码片段)
题目如下： 这道题我们最先想到的做法，应该就是2重循环枚举数对，然后把数对放在set里去重，最后输出set的大小，即输出set.size()。代码如下：1#include<iostream>2#include<set>3usingnamespacestd;45intn,k,a[100000];6s... 查看详情
怎么在今日头条上发布新闻，或者做广告投放的?
怎么在今日头条上发布新闻，或者做广告投放的?就是把信息，主动推送给用户的那种广告，或者新闻。广告投放自己不好做，要说自己在上边发新闻或许还可以今日头条如何发布文章？第一步，登陆今日头条官网申请账号第二... 查看详情
今日头条和今日头条极速版有什么区别
3C数码您的浏览器不支持HTML5视频zymedia(\'video\')参考技术A今日头条和今日头条极速版区别为：安装包大小不同、占用运行内存不同、特色功能不同。一、安装包大小不同1、今日头条普通版：今日头条普通版的安装包大小为22.8M。2... 查看详情
从互联网大脑模型看腾讯与今日头条之争
2018年以来，今日头条与百度，腾讯产生激烈的竞争，6月20日，百度一名前员工因涉嫌违反竞业协议加入今日头条，被百度诉至劳动仲裁部门，而之前一个月，在5月份，今日头条以侵害作品信息网络... 查看详情
洛谷2018寒假集训tg第二次比赛第二题princessprincipal题解
这算不算泄题啊。。。被kkk发现会咕咕咕吧。题目大意：给定一个数列a，与常数n，m，k然后有m个询问，每个询问给定l，r。问在a[l]到a[r]中最少分成几段，使每段的和不超过k，如果无解，输出Chtholly样例：input：557232343344551524outp... 查看详情