如何查找/存储长度为n的数组的所有可能的非空子数组的最大/最小值？
我生成了数组的段树，并为每个可能的子数组生成了if-do查询到段树，但这不是有效的我怎样在O（N）中做？
P.S n<=10^7
For eg. arr[]= { 1, 2, 3 }; // the array need not to be sorted
sub-array min max
{1} 1 1
{2} 2 2
{3} 3 3
{1,2} 1 2
{2,3} 2 3
{1,2,3} 1 3
最佳答案
我认为不可能把所有这些值都存储在o（n）中。但是在O（n）中，很容易创建一个结构，它可以回答O（1）中的查询：“有多少子集在那里[i]是最大元素”。
天真的版本：
考虑一下天真的策略：要知道某个a[i]有多少这样的子集，可以使用一个简单的o（n）算法，计算数组左右有多少元素小于a[i]。比如说：
A = [... 10 1 1 1 5 1 1 10 ...]
这个
5up在左边有3个元素，右边有2个元素小于它。从这里我们知道有4*3=12子数组，其中非常5是最大的。4*3因为左边有0..3子阵，右边有0..2子阵。优化版本：
这个天真的检查版本将对每个元素执行o（n）操作，因此毕竟是o（n^2）。如果我们能在一次传递中用O（n）计算出所有这些长度，不是很好吗？
幸运的是有一个简单的算法。用一堆就行了。正常遍历数组（从左到右）。将每个元素索引放入堆栈中但在放置之前，请删除其值小于当前值的所有索引当前索引之前的剩余索引是最近的较大元素。
要在右边找到相同的值，只需向后遍历数组。
下面是一个Python概念证明示例，展示了该算法的实际应用我还实现了天真的版本，因此我们可以交叉检查优化版本的结果：
from random import choice
from collections import defaultdict, deque
def make_bounds(A, fallback, arange, op):
stack = deque()
bound = [fallback] * len(A)
for i in arange:
while stack and op(A[stack[-1]], A[i]):
stack.pop()
if stack:
bound[i] = stack[-1]
stack.append(i)
return bound
def optimized_version(A):
T = zip(make_bounds(A, -1, xrange(len(A)), lambda x, y: x<=y),
make_bounds(A, len(A), reversed(xrange(len(A))), lambda x, y: x<y))
answer = defaultdict(lambda: 0)
for i, x in enumerate(A):
left, right = T[i]
answer[x] += (i-left) * (right-i)
return dict(answer)
def naive_version(A):
answer = defaultdict(lambda: 0)
for i, x in enumerate(A):
left = next((j for j in range(i-1, -1, -1) if A[j]>A[i]), -1)
right = next((j for j in range(i+1, len(A)) if A[j]>=A[i]), len(A))
answer[x] += (i-left) * (right-i)
return dict(answer)
A = [choice(xrange(32)) for i in xrange(8)]
MA1 = naive_version(A)
MA2 = optimized_version(A)
print 'Array: ', A
print 'Naive: ', MA1
print 'Optimized:', MA2
print 'OK: ', MA1 == MA2