kadane's algorithm ～最大部分和をO(N)～

ライブラリ

用途

  • 負の値も含みうる数値配列にて、隣接した部分和の最大値をO(N)で求める
  • 読み方はカダネではなく、ケイデインズ
  • 最大部分列和(maximum segment sum)と言われる

最大部分和問題

例1

1 2 3 -2 5の場合
answer : 9

例2

-2 1 -3 4 -1 2 1 -5 4
answer : 6

例3

-1 -2 -3
answer : -1

参考

https://ark4rk.hatenablog.com/entry/2018/01/08/002508

Quiz

https://practice.geeksforgeeks.org/problems/kadanes-algorithm/0/?ref=self

Submission

https://practice.geeksforgeeks.org/viewSol.php?subId=14333102&pid=106&user=peroon

Code

ll kadanes_algorithm(vector<ll> &A){
    ll ans = A[0];
    ll s = A[0];
    FOR(i, 1, A.size()){
        s = max(s + A[i], A[i]);
        chmax(ans, s);
    }
    return ans;
}

動画

www.youtube.com

問題