LeetCode 53題 最大子序和 — JavaScript
- 2019 年 10 月 4 日
- 筆記
解題思路分析：
該題是在一個整數數組中找到一個和最大的連續子數組，並返回和值。那麼如何找到一個和最大的連續子數組呢？我們知道，這肯定需要遍曆數組才行；好，那我們就開始遍曆數組。首先，我們初始化最大和 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 = -2， 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)
