ホームページ  >  記事  >  バックエンド開発  >  配列を指定して、配列内の最大の連続サブシーケンスの合計を見つけます。

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

王林
王林オリジナル
2019-10-29 09:19:313264ブラウズ

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

時間計算量は 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 サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。