1

次の2つのプロパティを持つリスト（少なくとも1つの正の整数を持つ）のサブリストを見つけようとしています1.その要素の合計が正です2.正の合計を持つ他のすべてのサブリストの最大長を持っています

私はそのリストの長さだけに興味があります。Kadaneのアルゴリズムは、O（n）時間で最大の合計を持つサブリストを見つけます。ここO（n）で同じことができるアルゴリズムはありますか？私は解決策を見つけましたが、それは実際にすべてのサブリストを計算し、もちろん非常に遅いです...。

お時間をいただきありがとうございます

4

4 に答える 4

0

OK、あなたはすでにほとんど答えています。サブシーケンスの合計ではなく、サブシーケンスの長さを使用するように Kadane を変更するだけです。それはあなたの問題を解決します。これはウィキペディアからのKadaneのです：

int sequence(int numbers[])    
{ 
    // These variables can be added in to track the position of the subarray
    size_t begin = 0;
    size_t begin_temp = 0;
    size_t len_temp = 0;
    size_t end = 0;

    // Find sequence by looping through
    for(size_t i = 1; i < numbers.size(); i++)
    {
            // calculate max_ending_here
            if(max_ending_here < 0)
            {
                    max_ending_here = numbers[i]; 
                    begin_temp = i;
            }
            else
            {
                    max_ending_here += numbers[i];
                    len_temp += (i - begin_temp);
            }

            // calculate max_so_far_len
            if(len_temp >= max_so_far_len )
            {
                    max_so_far_len  = len_temp; 
                    begin = begin_temp;
                    end = i;
            }
    }
    return max_so_far_len ;

}

于 2014-01-23T13:55:37.160 に答える
0

あなたの答えでは、サブリストを結果的な要素と見なしているので、Kadaneのアルゴリズムを少し変更するとうまくいくと思います。max_length_till_nowという名前の変数を導入するだけです。そして、現在の値よりも長い長さのサブリストが見つかったときはいつでも更新してください。

于 2014-12-14T06:50:51.710 に答える
0

考えられる解決策はここにあります。カウントソートを使用して、配列をソートできます。その後、最大の要素を見て合計を作成し、この要素を追加してもnotの正の合計が保持されるかどうかを確認し、正のままである場合はそれを追加し、カウントを増やします。これには、一部の入力にバグがある可能性があります。つまり、すべてのテストケースで機能しない可能性があります。ただし、これを改善すると目的の出力が得られるため、これは役立つアイデアにすぎません。1 つのトラバーサル カウント変数の最後に結果が得られます。例：

array=[12,10,8,5,4,-2,-3,-20,-30] //considered already sorted now
i=0 sum=12 count=1
i=1 sum=22 count=2
i=2 sum=30 count=3
i=3 sum=35 count=4
i=4 sum=39 count=5
i=5 sum=37 count=6
i=6 sum=34 count=7
i=7 sum=14 count=8
i=8 sum=14 count=8 //as now 30 cant be added
so, here count=8 says maximum length sub array of 8 can give you positive sum.
于 2013-11-03T09:52:27.910 に答える