找到最大子陣列

預處理爲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

回答