LeetCode 53題最大サブシーケンスと--JavaScript
1910 ワード
タイトルの説明:
整数配列
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を利用するのはサブ配列の連続を保証するためであり,sumに保存されている値は最大連続サブ配列の和である.
このアルゴリズムの時間的複雑さは,O(n)である.
このアルゴリズムの空間的複雑度はO(1)である.
関連リンク:https://leetcode-cn.com/problems/maximum-subarray/description/