最大サブアレイ

5252 ワード
algorithms python career java テキストリンク
これはLeetCodeと他のキュレート解決説明(インデックス)のシリーズの一部です.
あなたがこの解決が好きであるか、それが役に立つとわかるならば、このポストを好きにしてください.

Leetcode Problem #53 (Easy): Maximum Subarray


53章最大のサブアレイ


整数配列numsを与えて、最も大きい合計を持って、その合計を返す隣接したサブアレイ(少なくとも一つの数を含む)を見つけてください.
サブアレイは配列の連続した部分です.

例1 :


Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.


例2 :


Input: nums = [1]
Output: 1


例3 :


Input: nums = [5,4,-1,7,8]
Output: 23


制約


1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105


フォローアップ:O(n)ソリューションを考え出した場合は、別のソリューションをコード化してください.

解決策


この問題は、どのようにそれに近づくかによって複雑で簡単でありえます.
  • 私たちは、サブアレイを使用して可能な最大和を見つけるパターンを見つけることができます.
    最大合計は10右になりますか?

  • インデックス0から始まると言うことができますか
  • 最大合計upindexインデックス0 = 1
  • マックスサムアップインデックス2 = 3
  • 最大合計uptoインデックス3 = 6
  • 最大合計uptoインデックス4 = 10
    • それでは、楽しいものを加えましょう!
    現在、リストは1、2、3、4です
  • 最大合計upindexインデックス0 = 1
  • 最大合計uptoインデックス2 = previous MaxSum or current Value +previous MaxSum? = 1
  • 最大合計uptoインデックス3 = 4
  • マックスサムアップインデックス4 = 8
    • したがって、すべての数字を合計したとしても、値は8であることがわかります.
    もっと悪いことをしましょう
    - 2 , 1 , 3 , 4 , - 1 , 2 , 1 , 5 , 4
  • max sum upto index 0 =- 2/デフォルトでは最初の桁はMAX
    • です.
  • Max sum upto index 1 = -2 vs 1+-2 =- 1 WAITこの場合は、正の数が既にあれば、これは正しく見えません.
    OK、チェックの別の層を追加します.max = max(num[i], num[i-1]+num[i], maxSum)
  • 最大合計uptoインデックス1 = -2 vs 1+-2 vs 1 = 1!
  • マックスサムアップインデックス2 = 1 vs -3 vs -3 = 1
  • マックスサムアップインデックス3 = 1 vs 4-3 vs 4 = 4
  • マックスサムアップインデックス4 = 4 vs -1+4 vs -1 = 4
  • 最大合計uptoインデックス5 = 4 vs 2-1 vs 2 = 4 -再び待つ!4、- 1、2のシリーズはOKです、我々はちょうど最後の2つの値を取ることができない、我々はlocalsumの概念が必要です.So
    現在localMaxSum = nums[i] + Math.max(0, localMaxSum);
  • 最大合計uptoインデックス1 = 4 vs -1+2+4 vs 2 = 5!
  • マックスサムアップインデックス6 = 5 vs 5+1 vs 1 = 6
  • マックスサムアップインデックス7 = 6 vs 6-5 vs -5 = 6
  • マックスサムアップインデックス8 = 6 vs 6-5+4 vs 4 = 6

    • 実装


      public static int maxSubArray(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxSum = nums[0];
        int localMaxSum = nums[0];

        for (int i = 1, numsLength = nums.length; i < numsLength; i++) {
            localMaxSum = nums[i] + Math.max(0, localMaxSum);
            maxSum = Math.max(maxSum, localMaxSum);
        }

        return maxSum;
    }
}

    分析


    ASP.NET DataBase
    SpringbootプロジェクトredisTemplate快速有効操作redis