14

A(正と負の) 整数を含む配列があります。要素の絶対合計が最小である (連続した) サブ配列を見つけます。

A = [2, -4, 6, -3, 9]
|(−4) + 6 + (−3)| = 1 <- minimal absolute sum

正しい結果が得られましたがO(N^2)、 orであったブルートフォースアルゴリズムを実装することから始めました。O(N^3)ただし、タスクは次のように指定します。

complexity:
- expected worst-case time complexity is O(N*log(N))
- expected worst-case space complexity is O(N)

いくつか検索した後、この問題に合わせて Kadane のアルゴリズムを変更できるのではないかと考えましたが、失敗しました。

私の質問は - Kadane のアルゴリズムは正しい方法ですか? そうでない場合は、正しい方向に向けていただけますか (または、ここで役立つアルゴリズムを挙げてください)。既製のコードは必要ありません。適切なアルゴリズムを見つけるための助けが必要なだけです。

4

10 に答える 10

7

これは、Saksow のアルゴリズムの C++ 実装です。

int solution(vector<int> &A) {
    vector<int> P;
    int min = 20000 ;
    int dif = 0 ;
    P.resize(A.size()+1);
    P[0] = 0;
    for(int i = 1 ; i < P.size(); i ++)
    {
        P[i] = P[i-1]+A[i-1];

    }
    sort(P.begin(),P.end());
    for(int i = 1 ; i < P.size(); i++)
    {
         dif = P[i]-P[i-1];
         if(dif<min)
         {
             min = dif;
         }
    }
    return min;
}
于 2016-02-17T23:25:35.453 に答える
5

私は Codility でこのテストを行っていましたが、mcdowella の回答が非常に役立つことがわかりましたが、私が言わなければならないことは十分ではありません。

P[0] = 0、P[1] = P[0] + A[0]、P[2] = P[1] + A のように、配列 A (ここでは P と呼びます) のプレフィックス合計を作成する必要があります[1], ..., P[N] = P[N-1] + A[N-1]

A の「最小絶対合計」は、P の 2 つの要素間の最小絶対差になります。そのため、.sort()P を実行して、2 つの連続する要素を取得するたびにループする必要があります。このようにして、O(N + N log(N) + N) が得られ、これは O(N log(N)) に等しくなります。

それでおしまい！

于 2015-03-05T23:47:00.890 に答える
2

答えはイエスです。Kadane のアルゴリズムは間違いなく問題を解決するための方法です。

http://en.wikipedia.org/wiki/Maximum_subarray_problem

ソース - 私は、博士論文全体が最大サブアレイ問題に専念している博士課程の学生と緊密に協力してきました。

于 2014-09-22T02:50:21.017 に答える