配列の最大部分集合の和を求める

Question

私は1つのCS問題を解決しています。すなわち、N < = 100000となるサイズNの配列を与え、配列は負の整数と正の整数の両方を持ちます。配列の最大部分集合の合計、またはより正式には、これらの要素間の要素の合計が最大限になるようにインデックスiとjを見つける必要があります。

N = 5、array = {12、-4、-10,4,9}、answer = 13これは4 + 9が得られる最高のためです。

これは二次的な時間でbruteforceによって解決できることがわかりますが、これを対数的に線形に解くことができるのだろうかと思います。

ありがとうございます。

Answer 1

thisプレゼンテーションによると、Kadaneのアルゴリズムは、明らかに線形実行時バインドを生成します。そこから取られたC++の実装は次のようになります。

int maxSubArraySum(int a[], int size) 
{ 
    int max_so_far = INT_MIN, max_ending_here = 0; 

    for (int i = 0; i < size; i++) 
    { 
     max_ending_here = max_ending_here + a[i]; 
     if (max_so_far < max_ending_here) 
      max_so_far = max_ending_here; 

     if (max_ending_here < 0) 
      max_ending_here = 0; 
    } 
    return max_so_far; 
}