arrays - 配列内の要素の最大合計を見つける

Question

指定された整数値の配列 (負の整数を含む) を使用して、配列内の連続する要素の最大和を求めるプログラムを作成してください。

例：

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

与える

11

O(N^2) よりも高速なソリューションを探しています。

Answer 1

かだねのアルゴリズムはあなたが望むものだと思います

Answer 2

これは実際に私が大学で勉強した教科書の問題です (Mark Allen Weiss による 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;
}