关键词：
时间限制：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
输出例子1:
36
Ideas
最简单的暴力法直接两层循环，但是不用想，肯定超时。
区间问题一般有两种解法，一种是滑动窗口，用双指针不断尝试，一种是区间伸缩，尝试以数组中每一个数为中心，在满足要求的前提下向外扩展。
详细来说，对于数组的每一个数，以它为区间最小值都对应一个最大值区间，那么以第i个数为中心，分别向左右两边伸展，直到遇到比该数更小的数为止，即可伸展得到一个区间。
在伸展的过程中同时可以累加遍历到的数，这样伸展结束后可以直接将该数与累加和相乘，得到区间最大值。
Code
Python
- 暴力法
if __name__ == '__main__':
n = int(input())
nums = list(map(int, input().split()))
ans = 0
for i in range(n):
for j in range(i + 1, n):
min_num = min(nums[i:j])
total = sum(nums[i:j])
ans = max(ans, min_num * total)
print(ans)
- 区间伸展法
def solve2():
res = 0
for i in range(n):
if nums[i] != 0:
sum_tmp = nums[i]
left = right = i
while left - 1 > -1 and nums[left - 1] >= nums[i]:
sum_tmp += nums[left - 1]
left -= 1
while right + 1 < n and nums[right + 1] >= nums[i]:
sum_tmp += nums[right + 1]
right += 1
res = max(res, nums[i] * sum_tmp)
return res
if __name__ == '__main__':
n = int(input())
nums = list(map(int, input().split()))
print(solve2())
❤️tiktok字节跳动编程题实战2022校招——吐血分享总结。(代码片段)
❤️TikTok字节跳动编程题实战2022校招——吐血分享总结。前言+说明一、算法编程题（种树）二、算法编程题（小A的吃鸡之旅）三、算法编程题（有序最大K位数）四、算法编程题（测试计划的最大... 查看详情
2021校招字节跳动提前批
字节跳动提前批目录字节跳动提前批内容项目Java基础算法计算机网络设计模式数据库Linux总结时间：2020-07-0918:00-19:00内容项目背景：基于ZooKeeper的配置中心问题：项目的背景如何实现分布式锁的实现Java基础问题：HasMap的数据结... 查看详情
极客日报：腾讯启动最大规模校招；字节跳动否认“重启上市计划”传闻
...品|CSDN（ID：CSDNnews）一分钟速览新闻点！字节跳动否认“重启上市计划”传闻腾讯网启用新域名”QQ.中国”腾讯回应微视裁员：消息不实，系公司业务调整小米MIX4设计曝光：潜望三摄、全陶瓷机身华为... 查看详情
字节跳动2-1三轮大数据方向算法20220330(代码片段)
新鲜出炉，大数据的总监，一上来什么都没问，让我写一个非递归后续遍历。很不好意思让他打脸了，这个题我做过5片了，理解上还是很深刻的。我就想对他说为啥面试连自我介绍都不给我，就让我做题&#... 查看详情
求职字节跳动2019校招机器学习算法工程师面试
面试问题总结。 问题：1.自我介绍。2.介绍了一下自己简历上的项目。3.SVM详细原理。4.Kmeans原理，何时停止迭代。算法题：1.一个随机整数产生器产生[1，5]，如何设计一个产生[1，7]的随机整数产生器。解法：设k1，k2属于[1,5]... 查看详情
字节跳动面试笔试总结——算法岗位
目录1.一棵二叉树，求最大通路长度（即最大左右子树高度之和） 查看详情
字节跳动2-1三轮大数据方向算法20220330(代码片段)
新鲜出炉，大数据的总监，一上来什么都没问，让我写一个非递归后续遍历。很不好意思让他打脸了，这个题我做过5片了，理解上还是很深刻的。我就想对他说为啥面试连自我介绍都不给我，就让我做题&#... 查看详情
爱奇艺2018秋季校招算法工程师（第一场）
欢迎forkandstar：Nowcoder-Repository-github括号匹配深度题目：链接：https://www.nowcoder.com/questionTerminal/a2d5b1875bb0408384278f40d1f236c9来源：牛客网一个合法的括号匹配序列有以下定义:1、空串""是一个合法的括号匹配序列2、如果"X&q... 查看详情
题解百度2020校招web前端工程师笔试卷（第一批）：单选题多选题(代码片段)
...为各页加以编号，从0开始，若某一计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4字节，若使用一级页表的分页存储管理方式，逻辑地址结构为页号（20位），页内偏移量... 查看详情
手把手教你写！字节跳动正式启动2021届秋季校招
正文这次写一下springboot与redis的结合，这里使用的是redis集群模式（主从），主从环境的搭建，请参考redis集群搭建搭建完redis集群环境后，开始springboot之旅1、REDIS介绍redis的介绍及应用场景参考redis介绍2、... 查看详情
字节跳动算法整理(代码片段)
目录无重复字符的最长子串最长公共前缀*简化路径复原IP三数之和岛屿的最大面积搜索旋转排序数组朋友圈接雨水反转链表两数相加合并K个升序链表买卖股票的最佳时机买卖股票的最佳时机II最大子序和最小栈LRU缓存机制x的平... 查看详情
字节跳动高频算法题top100
题目出现次数3.无重复字符的最长子串10625.K个一组翻转链表84206.反转链表83215.数组中的第K个最大元素81146.LRU缓存机制68103.二叉树的锯齿形层次遍历6415.三数之和62121.买卖股票的最佳时机61160.相交链表581.两数之和48236.二叉树的最... 查看详情
今日头条2018校招后端方向（第二批）第一题二分查找(代码片段)
原题链接 https://www.nowcoder.com/test/8537209/summary题意n个数 q个查询 L,R,K L到R区间内为K的数有多少个数据范围 n<=300000,q<=300000 解析 对于每次查询必须要O(logn)复杂度才行 所以想到二分查找 因为数... 查看详情
2018秋招校招后端方向（第二批）(代码片段)
用户喜好 为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用... 查看详情
字节跳动技术新人培训全记录：校招萌新成长指南
...培训，让校招同学惊喜到要「再来一次」？潜入字节跳动技术新人培训「星火计划」现场，全程围观之后，技术范儿小编发现在这场活动上：不仅能从全盘了解了字节跳动到底是如何做技术的；更能学到如... 查看详情
美团点评2020校招算法工程师方向笔试题(代码片段)
...更好了QAQ。我是真的菜。。 试题链接：2020校招算法工程师方向笔试题 5、 外卖小哥的保温箱题意：众所周知，美团外卖的口号是:”美团外卖,送啥都快”。身着黄色工作服的骑手作为外卖业务中商家和... 查看详情
字节跳动抖音电商2-2算法20220331(代码片段)
题目：////n==nums.length//1<=n<=104//0<=nums[i]<=n//nums中的所有数字都独一无二//给定一个包含[0,n]中n个数的数组nums，找出[0,n]这个范围内没有出现在数组中的那个数。//输入：nums=[3,0,1]//输出 查看详情
字节跳动面试经验汇总
...之后就重新规划了一下自己的职业方向，最终目标定在了字节跳动，比较年轻化的一家互联网公司，近几年的发展速度也比较快，综合方面来说比较适合自己，所以就投了字节的简历，Java研发方向的，之后接到面试通知，总共... 查看详情