[問題] dna序列密度

[makiyolove (暴力熊)]

在網路上看到的題目

DNA序列是由A、T、C、G組成一串字串序列

舉例:agGCTGCAatGACAGTTGGG

然後找出大於使用者輸入長度L

包含C、G密度最高的序列串

此題解應輸出gGCTGC (假設L=5)

我只有想到用暴力法

列出每一種組合 計算密度 比較大小 再輸出

應該有更快的方法可以用?

懇請板友指教

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 192.192.199.49
推 march20:DP
推 march20:先求出 A1~Ai 的CG 個數合, 然後對所有
推 march20:max (S_i - S_(i-L+1)) for L<i<n
推 march20:啊, 直接回文
推 wa120:李家同Algorithms的書 多的是這種解題～
→ wa120:沒記錯的話是LCS problem
推 sorryChen:對阿 不是趙老師和呂學一老師論文嗎