※ 引述《FRAXIS (喔喔)》之銘言： : 這算是經典的最大連續子陣列和的變形吧。 : 給定一個長度為 n 的整數陣列，和一個正整數 k 。 : 找出一個在所有 C(n, 2) 個連續子陣列中，總和第 k 大的連續子陣列。 : 理論上是可以做到 O(n)，但是這方法應該不實用。 : 雖然也有其他的O(n lg n)，O(n lg^2 n)和O(n lg^3 n)的方法， : 但是好像都不太實際 （O(n lg^3 n)的方法或許比較可行..） : 我的問題是： 有沒有實際上比較有效率（o(n^2)）且好實作的方法呢？ : 這問題是在 careercup 上看到的面試問題 : http://www.careercup.com/question?id=12804676 最近剛好有遇到類似的問題 我想你問的應該是靜態問題而不是動態問題吧？ 令 sum[i][j] = a[i] + ... + a[j] 是連續和 把 sum 畫成一個矩陣 只有上三角，對角線是 a[0] 到 a[n-1] 整個結構類似 pascal 三角形， 不過這裡是越右上越大，右上角是總和 a[0] + ... + a[n-1] 目標是從上三角當中找到第k大 之前在這個板有討論過一個類似的問題：已排序陣列找第k大、row已排序陣列找第k大 ┌─────────────────────────────────────┐ │ 文章代碼(AID): #1KF5PfAs (Prob_Solve) [ptt.cc] [問題] 給定n個排好序的整? │ │ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1413240425.A.2B6.html │ │ 這一篇文章值 107 Ptt幣 │ └─────────────────────────────────────┘ 應該就是這樣解吧？ 只不過這個問題的陣列元素不是已知 所以要先算個前綴和，就能以O(1)時間求得陣列元素 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.79.38 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1425079575.A.53B.html ※ 編輯: DJWS (111.250.79.38), 02/28/2015 07:34:55 ※ 編輯: DJWS (111.250.79.38), 02/28/2015 07:46:31