配列内の要素の最大和を求める整数値の配列（負の整数を含む）によって、配列内の連続する要素の最大合計を求めるプログラムを記述する。

例：

2、3、-6、-1、2、-1、6,4、-8、8

は

を与えます11

私は解決策を探していますrはO（N^2）より大きい。

出典

2012-09-09 user1106337

1,2,5,6は連続していません。あなたが取ることができるサブセットに制限がないなら、これはNP-Complete問題であるSubset-Sum問題ですが、そうは思わないでしょう。 – amit

誤解をおかけして申し訳ありません。私は説明と例で間違いを犯しました。 :)私は両方を更新しました。 – user1106337

リニアスキャンでこの問題を解決できます。 sum <0の場合は合計して現在のmaxと比較し、sumを0にリセットして続行します。この貪欲な解決策は正しいことが証明されています。これはKadaneのアルゴリズムと呼ばれています：http://en.wikipedia.org/wiki/Maximum_subarray_problem – nhahtdh

、私はそれは非常に美しく、エレガントなソリューションと解きです... Kadane's Algorithmはあなたが

出典

2012-09-09 13:12:08 Qyrus

リンクはもはや有効ではありません – fayyazkl

これは実際に私が（マーク・アレンワイスによってC内のデータ構造とアルゴリズム）を大学で研究教科書の問題で欲しいものだと思いますO（N）

int MaxSubsequenceSum(int A[]) 
{ 
    int sum = 0, maxSum = 0; 

    for (int j = 0; j < A.Length; j++) 
    { 
     sum = sum + A[j]; 

     if (sum > maxSum) 
      maxSum = sum ; 
     else if (sum < 0) 
      sum = 0; 
    } 
    return maxSum; 
}

出典

2012-09-09 14:08:08

あなたの投稿は匿名ユーザーによって編集され、承認されました。これらの変更が実際にはポジティブであることを確認できますか？ロジックを大幅に変更したようです。 – Gray

いいえ私はそれを承認しなかったし、それは答えを大きく改善しない。私はそれがポイントのために行われたと思う –

匿名ユーザーによって行われたので、代理人は授与されませんでした。自由にロールバックしてください。彼らはなぜ彼らがそれをしたのかについてコメントしました（http://stackoverflow.com/posts/12339772/revisions）。 – Gray

-1

に最初降順に指定された配列を並べ替えることができ、次いでによってアレイの最初の3つの要素をまとめる：sum=0とプリント和をintializingによって sum=arr[0]+arr[1]+arr[2] 。

出典

2014-06-12 20:14:35 bitsk

配列内の要素の最大和を求める整数値の配列（負の整数を含む）によって、配列内の連続する要素の最大合計を求めるプログラムを記述する。

答えて

関連する問題