题解：字节跳动-编程题2

同志们想复杂了，用的方法既满又难写，实际上解法还是很简单的。
注意这道题有一个限制：数字都在[0, 100]的范围内，这其实可以拆解为两点：
1.值非负，这决定了我们的算法
2.值小与100，这省了我们很多事，对笔试非常友好。

注意看目标函数：区间中的最小数 * 区间所有数
一个非常自然的想法是我们从小到大遍历数值，这样“区间的最小数”就确定了。
然后我们考虑区间有多大，显然，由于值非负，区间等于：[向左直到遇到已经插入的点,向右直到遇到已经插入的点]
由于我们是从小到大添加的数，那么实际上就是找：最大的比他坐标小的分割点，最小的比它坐标大的分割点，这是典型的平衡二叉树。时间复杂带
但是，平衡二叉树对于python而言是不现实的，幸亏题目限制了只有100个值，允许我们进行100次线性扫描。时间复杂度
故：

n=int(input())
inp=[int(x) for x in input().split()]
buckets=[ [] for i in range(101)] ## buckets[value]保存了所有值为value的点
sm=[0] ## sm是用来计算区间和的 sum(inp[a:b])=sm[b]-sm[a]
for i in range(len(inp)):
    sm.append(sm[-1]+inp[i])
    buckets[inp[i]].append(i)
sm.append(1E1000)
ans=0
pat=[-1,len(inp)] ## 保存已经添加的分割点
for bid,b in enumerate(buckets):
    b.sort()
    itr=0
    for p in b:
        #寻找区间的两端
        while p>=pat[itr]:
            itr+=1
        ans=max(ans,bid*( sm[pat[itr]] - sm[pat[itr-1]+1]    ))
    ## 将新的分割点加入pat(tern)数组
    pat=sorted(pat+b) ## 原则上应当用O(n)的方式合并两个有序数组，我这里懒了
print(ans)