シーケンス内の指定された長さのサブシーケンスを見つけて、そのサブシーケンスの合計が最大になるようにするにはどうすればよいですか？

-1

例：シーケンスを= {1,8,2,9}、サブシーケンスの長さ= 2とすると、得られる最大合計はサブシーケンス{8,9}から得られ、その合計8 + 9 = 17です。このためのアルゴリズムを作成するにはどうすればよいですか？シーケンス内の指定された長さのサブシーケンスを見つけて、そのサブシーケンスの合計が最大になるようにするにはどうすればよいですか？

出典

2017-01-22 Sourabh Khandelwal

配列内のK個の最大要素を見つけることとはどのように違いますか？ – dasblinkenlight

シンプルなアルゴリズム（Lukによって既に与えられているような）、長いシーケンスの高速アルゴリズム、長いサブシーケンスの高速アルゴリズム、またはその他のアルゴリズムを使いたいですか？これまでのところどのような仕事をしていますか？ [FAQ]（http://stackoverflow.com/tour）と[How to Ask]（http://stackoverflow.com/help/how-to-ask）を参照してください。 –

私は、この質問を完全にはっきりさせておらず、質問者に示された作業がないので、この質問をトピックとして閉じようとしています。 –

簡単です。

2つの最も高い数字を維持してシーケンスをスキャンするだけです。擬似コード：ループ出力平方メートル+ M1

後

Initialize m1 and m2 to lowest possible element (0 or -max int) 
for each item in the sequence: 
    if item > m1 then 
    m2 = m1 
    m1 = item

これは、2つの要素よりも小さいシーケンスを考慮して取ることはありませんが、あなたは簡単にこのエッジケースを追加することができます。

2の代わりにKを使用する場合は、2つの変数の代わりにK要素のcollection（配列）を使用します。

これはO（n）です。

出典

2017-01-22 11:29:04

実際には、 'k'（部分列内の要素の数）が大きければ、それははるかに高い次数になります。正確な順序は現在の最も小さい保存値を調べる方法に依存します。保存したリストに新しい値を追加します。これらは、現在保存されている最大値を格納するデータ構造に主に依存します。与えられたアルゴリズムはシンプルですが、大きな 'k'では最も速くはありません。 –

シーケンス内の指定された長さのサブシーケンスを見つけて、そのサブシーケンスの合計が最大になるようにするにはどうすればよいですか？

答えて

関連する問題