KadaneのアルゴリズムによるO（N）の最小和サブアレイ

Question

私たちはすべて、最大和サブアレイと有名なKadane's algorithmについて知っています。しかし、同じアルゴリズムを使って最小合計を見つけることはできますか？

私のテイクは以下のとおりです。

は符号を変更して、我々は最大の和サブアレイを計算する方法と同じことで、最大の合計を、見つける。配列内の要素 の符号を変更して初期状態にします。

問題が発生した場合は、修正をお手伝いしてください。

コーナーケース：私はすべての要素が肯定的である場合、いくつかの前処理を行うことで問題を処理できることを知っています。つまり、すべてが+ veであれば配列を走査します。

上記のアルゴリズムはうまく機能し、よくサポートされます（dasblinkenlight）。

Answer 1

最小の合計を見つけるために私が言及したアプローチはありますか？

はい、そうです。最小絶対値を持つ負の合計を見つけることとして、最小合計を見つける問題を再記述することができます。数字の兆候を切り換えて残りのアルゴリズムをそのまま維持すると、それがアルゴリズムがあなたに返す数字です。

すべての要素が

正である場合、私は問題が存在しているはずはありません、何も問題はありません：すべての要素が負の場合、元のKadaneのアルゴリズムを検討します。この場合、アルゴリズムはゼロの合計のために空のシーケンスを返す - 状況の中で可能な最高のシーケンス。言い換えれば、すべての要素が負の場合、あなたの最良の解決策はそれらのどれも取らないことです。

あなたの変更されたアルゴリズムは、すべての数字が正の場合に同じことを行います：もう一度、あなたの最良の解決策は数​​字を一切取らないことです。

アルゴリズムから返された範囲が空ではないという要件を追加すると、Kadaneのアルゴリズムが空の範囲を返す場合にアルゴリズムをわずかに修正して、最小の正の数（または最大の負の数）を見つけることができます最適なソリューションとして。

Answer 2

maxをminに置き換えます。

//O(n) 
public static int minSubArraySum(int[] arr) { 
    int minSum = 0; 
    int curSum = 0; 
    for (int i : arr) { 
     curSum += i; 
     minSum = Math.min(minSum, curSum); 
     curSum = Math.min(curSum, 0); 
    } 
    return minSum; 
}