配列を指定して、配列内の最大の連続サブシーケンスの合計を見つけます。-PHPの問題-php.cn

配列を指定して、配列内の最大の連続サブシーケンスの合計を見つけます。

王林

リリース： 2023-02-27 21:58:01

オリジナル

3261 人が閲覧しました

配列を指定して、配列内の最大の連続サブシーケンスの合計を見つけます。

時間計算量は O(n)

配列を 1 回処理するだけで済みますが、本質的な事項を深く理解する必要があります。この配列の特性、つまり動的計画法の手法です。

最初に、thisSum と maxSum という 2 つの変数を設定します。このうち、thisSum は現在位置に到達する要素の合計を表し、maxSum は現在位置に到達する連続するサブシーケンスの最大合計を表します。

注: thisSum が負の場合は、直接 0 に設定します。thisSum が maxSum より大きい場合は、maxSum を thisSum の値に設定します。

public static int maxSubArray(int[] nums)
    {
        int length = nums.length;
        if(length <= 0)
            return 0;
        int CurSum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < length; i++)
        {
            if(CurSum <= 0)     //当当前的和小于等于0，那么就给其置为当前元素的值
                CurSum = nums[i];
            else
                CurSum += nums[i];
            if(CurSum > max)
                max = CurSum;
        }
        return max;
    }

ログイン後にコピー

推奨チュートリアル: PHP チュートリアル

以上が配列を指定して、配列内の最大の連続サブシーケンスの合計を見つけます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。