找到最大子阵列

预处理为O的阵列关于A（n log n）的时间，以便可以回答的形式 findmax（I，J）的查询：找到在一个间隔的最大值[I; （即，O（1）中的数组元素A [i]，A [i + 1]，...，A [j]）中的最大值）。找到最大子阵列

其他问题：显示如何在预处理O（n）的时间，这样就可以回答澳上面查询（log n）的时间。

2013-02-24 1234

你到目前为止尝试过什么？现在它看起来像您复制并从问题集或编码的挑战网站，这让我们很没有理由希望能帮助您在所有逐字粘贴这个问题。 – templatetypedef 2013-02-24 19:31:58

我试过DP，这是过去一年的信息奥林匹克问题。 :) – 1234 2013-02-24 19:44:09

该问题被称为范围最小（最大）查询 - RMQ。链接基本上回答你的两个问题。

经典的解决方案是动态编程和分段树。

2013-02-24 19:39:52 IVlad

回答