※ 引述《makiyolove (暴力熊)》之銘言：
: 在網路上看到的題目
: DNA序列是由A、T、C、G組成一串字串序列
: 舉例:agGCTGCAatGACAGTTGGG
: 然後找出大於使用者輸入長度L
: 包含C、G密度最高的序列串
: 此題解應輸出gGCTGC (假設L=5)
: 我只有想到用暴力法
: 列出每一種組合 計算密度 比較大小 再輸出
: 應該有更快的方法可以用?
: 懇請板友指教
1.
開一個陣列s[]，s[i]的值是原字串中累加到第i個字元中，有幾個C,G
我們要找的是一組(i,j)使得 m = (s[j]-s[i])/(j-i) 有最大值，且j-i>L
底下的方法中，假設已知m的最大值，然後檢查是否有>=m的(i,j)
若有則增加m的值，反之則減少
2.
設平面座標點 (x,y) = (i,s[i]-m*i)
於是若有 y2>=y1 且 x2-x1>L 的點 (x1,y1),(x2,y2)
則代回後就有 s[j]-m*j>=s[i]-m*i，即有 (s[j]-s[i])/(j-i)>=m，這樣的(i,j)
所以現在的目標是要尋找重設後的點中 y2>=y1 且 x2-x1>L 的 (x1,y1),(x2,y2)
3.
對於每個點(x,y)，新增一個點(x',y')=(x+L,y)
將所有舊點(x,y)和新點(x',y')全部混在一起，依x座標非遞減排序後
依序檢查每個點，設Y為當前最大的y'值
若目前檢查到的點是新增後的點(x',y')且y'>Y，則更新Y=y'
若目前檢查到的是舊點(x,y)，則檢查是否有y<=Y，若是則存在y2>=y1且x2-x1>L
即這次假設的最大值m是存在相應的(i,j)的
要注意的是，排序時若有x座標相等的情況，則舊點需排在新點之前
4.
對於m值的尋找，是可以binary search的，設m=(min+max)/2
若存在>=m的(i,j)，則設 min=m，反之設max=m
5.
步驟3的檢查是O(N)的，其中的排序可以預處理 (N是字串長度)
步驟4的binary search是O(logW)的，其中W的值視答案要求的精確度而定
總時間複雜度是 O(NlogW)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.70.137.244