推 LPH66: a 陣列元素好像沒說一定是正的... 02/28 08:19
→ DJWS: 對耶 爆了 枉費我打那麼多字 02/28 08:21
→ DJWS: 這樣的話 也許要先想辦法找到等於零的連續和在哪些地方 02/28 09:00
※ 引述《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://www.ptt.cc/bbs/Prob_Solve/M.1413240425.A.2B6.html │
│ 這一篇文章值 107 Ptt幣 │
└─────────────────────────────────────┘
應該就是這樣解吧？
只不過這個問題的陣列元素不是已知
所以要先算個前綴和，就能以O(1)時間求得陣列元素
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.79.38
※ 文章網址: https://www.ptt.cc/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