8

アルゴリズムに関する質問があります。

サイズNの配列（すべての要素が整数であると仮定）が与えられた場合、最大のドロップ（必ずしも連続的である必要はありません）を見つけます：max {array [i] -array [j]}制約付き：i>j。

単純な解決策は、2つのループがあり、iとjのすべての可能な値を通過することですが、時間計算量はO（n * n）です。

そして、私が思う改善された解決策は、最初に配列のインデックスをマップし、配列をソートし、配列を調べて最大のドロップを見つけることです。この複雑さはO（nlogn）です。

線形時間計算量のソリューションはありますか？そしてどうやって？

PS：私はかつて線形ソリューションを考えていました：2つの追加の配列を作成します.1つは指定された配列の最大値を最初から最後まで記録し、もう1つは最小値を最後から最初まで記録することです。 2つの配列1つのパス。しかし、誰かが正しくないと思って、あまりにも大きなスペースを占めていました。だから私はより良い解決策を知りたいです。–lijuanliu

4

5 に答える 5

5

次の 2 つのことを追跡する必要があります。

あなたが持っている最大数は要素 i までと思われ、あなたが持っている最大のドロップは最大数 (つまり、i の前の最大数から要素 i を引いたもの) に関して見えます。これは、時間では O(n)、空間では O(1) になります。

この問題はまさに「株の売買」インタビューの質問です。解決策はここにあります:最大の単一販売利益

于 2013-02-22T08:41:53.877 に答える
5

余分なスペースのない O(n) ソリューション:

public int maxDrop(int[] a) {
    int max = a[0];
    int maxDrop = -1;
    for (int i = 0; i < a.length; i++) {
        if (max < a[i]) {
            max = a[i];
        }
        else {
            int drop = max - a[i];
            maxDrop = Math.max(maxDrop, drop);
        }
    }
    return maxDrop;
}
于 2015-08-22T22:33:56.840 に答える
4

新しい 2 つの配列を作成します。

max[i] = max { arr[0], arr[1], ..., arr[i] }
min[i] = min { arr[n-1], arr[n-2], ..., arr[i] }
(max is the maximum from first to i, min is the minimum from i to last)

ここで、補助配列を反復し、最大の差を見つけますmax[i] - min[i]

これには全体で 3 回の反復が必要であり、したがってO(n).

正当性の証明 (ガイドライン):

最大のドロップを index から indexiにしますj。ここで、i<j:

  1. 次に、max[i] >= arr[j]（すでに合格しているため）、さらに min[i] <= arr[i]- したがってmax[j] - min[j] >= arr[i] - arr[j]、アルゴリズムによって提供される答えは、少なくとも最適と同じくらい良いです。
  2. また、最大のドロップはであるため、 そのようなものi,jは存在しません。最大のドロップは から までになるからです。同様に -同じ理由で、そのようなもの はあり得ません- したがってk<jarr[k] < arr[i]arr[k]arr[j]k>jarr[k] < arr[j]max[j]-min[j] <= arr[i] - arr[j]

以上のことから、max[j]-min[j] = arr[i] - arr[j]. 正式な完全な証明のために残されているのは、それぞれに対してkが得られることを示すことであり、これは実際max[k]-min[k] <= max[j] - min[j]にそうです。u<kv>kmax[k]=arr[u], min[k]=arr[v]arr[u] - arr[v] > arr[i] - arr[j]i,j

QED

于 2013-02-22T08:42:52.457 に答える
-1

私は O(nlogn) しか考えられませんが、これは同じ複雑さでソートして最大のドロップを見つけるよりも高速である必要があります。

あなたができることは、O(n) の連続した数値の差を計算することです。その後、問題は O(nlogn) になる連続したサブ配列の MAX(sum) を見つけることに軽減されます。

于 2013-02-22T08:38:49.197 に答える
-1 
public static int maxDrop(int[]array){

    int maxDrop =0,drop=0,min=array[0];

    for(int i=1;i<array.length;i++){

        if(array[i]<min){
            min=array[i];
        }

        drop = array[i]-min;

        if(drop>maxDrop){
            maxDrop=drop;
        }

    }

    System.out.println(maxDrop);
    return maxDrop;

}
于 2014-07-15T11:09:15.057 に答える