给定一个大小为n的数组A，我们需要求j-i的max，这样对于所有k，i我已经能够通过动态规划在o（n^2）中解决它。有更好的解决办法吗？
最佳答案
这是一个新的，经过测试的线性时间解。
下面的代码计算每个
前缀a[:j + 1]表示j从0到n - 1（存储在k中）。这个
stackstarts保存从s到0的索引，以便j对于从a[s] <= a[t]到t的所有s + 1，即
可以在索引j或之后开始有效子数组。堆栈j保存从blockers到s的索引，以便0
对于从j到a[s] > a[t]的所有t，即最小元素集
需要借助最后一个元素排除所有无效子数组
最大化。s + 1和j的维护需要摊销
恒定时间，因为每个循环迭代最多追加一个元素。
以索引starts结尾的有效子数组是那些以blockers中的指数大于除j以外的所有电流阻滞剂
本身天真的是，我们每次都可以向后扫描
合适的起始索引，但是我们可能平均扫描过多。
输入变量starts，将索引保存在j中
最近扫描过通过在i开始下一次扫描，我们确保
扫描的摊余成本是固定的，同时仍然扫描所有
可能长于starts的子阵。
import itertools
def longest(a):
k = 0
n = len(a)
starts = []
blockers = []
for j in range(n):
while starts and a[starts[-1]] > a[j]:
del starts[-1]
starts.append(j)
while blockers and a[blockers[-1]] <= a[j]:
del blockers[-1]
if blockers:
i = min(i + 1, len(starts) - 1)
while i > 0 and starts[i - 1] > blockers[-1]:
i -= 1
else:
i = 0
k = max(k, j + 1 - starts[i])
blockers.append(j)
return k
def longest_slow(a):
n = len(a)
for k in range(n, 0, -1):
for i in range(n - k + 1):
b = a[i:i + k]
if b[0] == min(b) and max(b) == b[-1]:
return k
return 0
def test():
for n in range(9):
for a in itertools.permutations(range(n)):
assert longest(a) == longest_slow(a)
test()