LeetCode 53題最大サブシーケンスと--JavaScript

タイトルの説明:

整数配列numsが与えられ、最大和を有する連続サブ配列(サブ配列は少なくとも1つの要素を含む)が見つかり、その最大和が返される.

例:

  : [-2,1,-3,4,-1,2,1,-5,4],
  : 6

メソッド分析:

この問題は、整数配列の中で最大の連続サブ配列を見つけ、和値を返すことです.では、どのようにして最大の連続サブ配列を見つけますか?配列を巡る必要があることを知っています.では、配列を巡り始めましょう.まず、最大とsumと現在とcurrSumを初期化し、currSumの場合、0未満の場合、配列の次の値を割り当てます.そうでない場合は、配列の次の値を加算します.次に、現在のsumとcurrSumの最大値を取ります.
抽象的に言えば、やはりコードで表現しましょう.

コード実装:

var maxSubArray = function(nums) {
  //    nums    
  if(nums){
    //      sum、   currSum
    var sum = nums[0];
    var currSum = nums[0];
    for (var i = 1; i < nums.length; i++) {
      //     currSum
      currSum = currSum < 0 ? nums[i] : currSum + nums[i];
      //     sum
      sum = Math.max(currSum,sum)
    }
    return sum;
  }
};

コード解析:

入力配列nums=[−2,1,−3,4,−1,2,1,−5,4]を例に,実行フローを解析する.

初期化:currSum=-2,sum=-

nums[1]:currSum=-2<0のため、currSum=nums[1]=1;sum = Math.max(1,-2) = 1,

nums[2]:currSum=1>0のため、currSum=currSum+nums[2]=-2;sum = Math.max(-2,1) = 1,

nums[3]:currSum=-2<0のため、currSum=nums[3]=4;sum = Math.max(4,1) = 4,

nums[4]:currSum=4>0のため、currSum=currSum+nums[4]=3;sum = Math.max(3,4) = 4,

nums[5]:currSum=3>0のため、currSum=currSum+nums[5]=5;sum = Math.max(5,4) = 5,

nums[6]:currSum=5>0のため、currSum=currSum+nums[6]=6;sum = Math.max(6,5) = 6,

nums[7]:currSum=6>0のため、currSum=currSum+nums[7]=1;sum = Math.max(1,6) = 6,

nums[8]:currSum=1>0のため、currSum=currSum+nums[8]=5;sum = Math.max(5,6) = 6,

サイクルが終了し、最終的にsum=6

に戻る
以上のプロセスの分析を行うことで、比較的明確になるはずです.一言で言えば,我々がcurrSumを利用するのはサブ配列の連続を保証するためであり,sumに保存されている値は最大連続サブ配列の和である.
このアルゴリズムの時間的複雑さは,O(n)である.
このアルゴリズムの空間的複雑度はO(1)である.
関連リンク:https://leetcode-cn.com/problems/maximum-subarray/description/