4

私はこの問題に関するあなたの考えを求めています：

doubleタイプ（または整数）の要素がN個ある配列Aが1つあります。複雑さがO（N 2）未満のアルゴリズムを見つけて、次のことを見つけたいと思います。

    max A[i] - A[j]

1 <j <=i<nの場合。はありませんのでご注意くださいabs()。私は考えました：

  • 動的計画法
  • 二分法、分割統治法
  • インデックスを追跡するソート後の処理

コメントやアイデアはありますか？そのようなアルゴリズムの質問を解決するためにトレーニングまたは進歩を遂げるためのいくつかの良い参考文献を指摘できますか？

4

4 に答える 4

8

アレイ全体を3回スイープします。最初に上から、これまでのところ最小限の要素でj=2補助配列aを埋めます。次に、上から下にスイープを実行し、これまでのところ（上から）最大要素で別の補助配列を（上から下に）埋めます。次に、両方の補助アレイのスイープを実行し、の最大差を探します。i=n-1bb[i]-a[i]

それが答えになります。O(n)合計で。動的計画法アルゴリズムと言えます。

編集：最適化として、3番目のスイープと2番目の配列を削除し、2つのループ変数max-so-far-from-the-topとmax-differenceを維持することにより、2番目のスイープで答えを見つけることができます。

このような問題を一般的に解決する方法に関する「ポインタ」については、通常、分割統治法、メモ化/動的計画法など、自分が書いたのと同じようにいくつかの一般的な方法を試します。まず、問題と関連する概念を詳しく調べます。ここでは、最大/最小です。これらの概念を分解し、問題のコンテキストでこれらの部分がどのように組み合わされ、計算される順序が変わる可能性があるかを確認してください。もう1つは、問題の隠れた順序/対称性を探しています。

具体的には、リストに沿って任意の内点を修正すると、この問題は、のようなすべてのsの最小要素と、sの最大要素kの差を見つけることになります。ここでは、分割統治法に加えて、最大/最小の概念（つまり、プログレッシブ計算）とパーツ間の相互作用を分解しています。非表示の順序が表示され（配列に沿って）、メモ化により、最大/最小値の中間結果が保存されます。j1<j<=kik<=i<nk

任意の点の固定は、k最初に小さなサブ問題を解決し（「与えられたk...」）、それについて何か特別なことがあり、それを廃止（一般化）して抽象化できるかどうかを確認することと見なすことができます。

元の問題がこの大きな問題の一部になるように、最初に大きな問題を定式化して解決しようとする手法があります。ここでは、各kのすべての違いを見つけ、それらから最大のものを見つけることを考えます。

中間結果の二重使用（特定のポイントの比較と、それぞれの方向での次のk中間結果の計算の両方で使用）は、通常、かなりの節約を意味します。それで、

  • 分割統治
  • メモ化/動的計画法
  • 隠された秩序/対称性
  • 概念を分解する-パーツがどのように組み合わされるかを見る
  • 二重使用-二重使用のパーツを見つけてメモ化します
  • より大きな問題を解決する
  • 任意のサブ問題を試し、それを抽象化する
于 2012-05-29T06:17:17.137 に答える
4

これは、1 回の繰り返しで可能になるはずです。max(a[i] - a[j])for 1 < j <= i は と同じはずmax[i=2..n](a[i] - min[j=2..i](a[j]))ですよね? したがって、配列を反復処理しながら最小のものを追跡a[j]し、最大のものを探す必要がありa[i] - min(a[j])ます。そうすれば、反復は 1 回だけで、j は i 以下になります。

于 2012-05-29T16:40:23.347 に答える
1

配列を調べて最大値と最小値を見つけて差を求めるだけなので、最悪のケースは線形時間です。配列がソートされている場合、一定の時間で差分を見つけることができますか、それとも何か見逃していますか?

于 2012-05-29T05:41:09.727 に答える
0

Java 実装は線形時間で実行されます

public class MaxDiference {

public static void main(String[] args) {
     System.out.println(betweenTwoElements(2, 3, 10, 6, 4, 8, 1));
}

private static int betweenTwoElements(int... nums) {
    int maxDifference   = nums[1] - nums[0];
    int minElement      = nums[0];

    for (int i = 1; i < nums.length; i++) {
        if (nums[i] - minElement > maxDifference) {
            maxDifference = nums[i] - minElement;
        }
        if (nums[i] < minElement) {
            minElement =  nums[i];
        }           
    }       
    return maxDifference;
}
}
于 2012-10-01T14:26:34.677 に答える