0
以下は、最大単調サブシーケンス（増加または減少のいずれか）のコードです。私はこれをコーディングする前に研究をしておらず、一般的なコンピュータサイエンスの質問であることに気づいていませんでした。その後の研究から、一般的に受け入れられている最も効率的なアルゴリズムはO（N log N）であると思われる。これらは、通常、現時点で私の頭の中に少し浮かぶ動的プログラミング型のソリューションです。最大単調増加または減少サブシーケンス
私はアルゴリズムのエキスパートではありませんが、次のコードはO（N）ではありませんか？私は各リストを2回、増加するシーケンスを見つけるために1回、減少のために1回ずつ渡します。
私は機能が非常に重複していることを理解していますが、2番目の機能/パスの繰り返しなしですべてを1つにする素晴らしい方法を見つけることができませんでした。
def largest_monotonic_subsequence(lst):
def increasing(lst):
beg,end,best = 0,0,[0,0]
for i in range(len(lst)-1):
if lst[i] <= lst[i+1]:
end = i+1
if end - beg > best[1] - best[0]:
best = beg, end
else:
beg = i+1
return (best[0],best[1]+1)
def decreasing(lst):
beg,end,best = 0,0,[0,0]
for i in range(len(lst)-1):
if lst[i] >= lst[i+1]:
end = i+1
if end - beg > best[1] - best[0]:
best = beg, end
else:
beg = i+1
return (best[0],best[1]+1)
incr = increasing(lst)
decr = decreasing(lst)
return lst[slice(*max([incr,decr], key = lambda x: x[1]-x[0]))]
比較の意味を逆にする+1または-1に設定サイン引数を、使用することができます" –
[数学]（https://en.wikipedia.org/wiki/Subsequence）のサブシーケンスは、残りの要素の順序を変更せずにいくつかの要素を削除することによって、別のシーケンスから派生できるシーケンスです。 [...]サブシーケンスをサブストリングと混同しないでください。 –
だから、この質問はMITのOCWクラスの一部で、私は私のSOを手伝っていました - 私はそれを解決した後、私は "単調増加テスト"のためにgoogledして、明らかにRTFMを十分に緊密にしませんでした。連続的なものが基準でない場合、なぜこれがより難しい問題になるのかはっきりと分かります。愚かな質問に対する謝罪。 – Solaxun