0

次の数値を考慮してください。

9,44,32,12,7,45,31,98,35,37,41,8,20,27,83,64,61,28,39,93,29,92,17,13,14, 55,21,66,72,23,73,99,1,2,88,77,3,65,83,84,62,5,11,74,68,76,78,67,75,69, 70、22、71、24、25、26。

リスト内の最小量の数字を削除してシーケンスを作成するアルゴリズムを実装しようとしています

a) 昇順 b) 降順

私はすでに最短と最長のサブセクションで試しました。コードは必要ありません。説明または疑似コードのみが必要です。問題の解決方法がわかりません。ありがとうございます。

4

2 に答える 2

2

これは軽くカモフラージュされた最長増加 (減少) サブシーケンス問題です。問題を解決するアルゴリズムは次のとおりです。

  • 配列内の最長の増加 (減少) サブシーケンスを見つける
  • 最長増加サブシーケンスに属さないすべての要素を削除します。

増加/減少するサブシーケンスが最も長いため、削除する数値の量は最小になります。

ウィキペディアの記事には、LIS/LDS 問題を解決するための優れた疑似コードがあります。元のシーケンスが 1000 要素以上の長さでない限り、バイナリ検索を線形検索に置き換えることができます。

于 2013-08-15T01:41:20.123 に答える
0

すでに言及されているので、2セント追加します。おそらく、このような状況では、実行時間 (効率) が大きな懸念事項である面接で尋ねられます。したがって、実行にかかる時間に応じて、多くのアルゴリズムで同じ問題に取り組むことができます。最もよく知られているアルゴリズムは、オーダー O(nlogn) です。その他の重要な例として、動的プログラミング パラダイムを適用して O(n^2) の解を得ることができます。

ここにO(n^2)

ここにO(nlogn)

于 2013-08-16T13:27:05.493 に答える