leetcode-Easy-第10期-陣列-Maximum Subarray
摘要:
求陣列中元素相加所能取得的最大值,這些元素必須相臨,複雜度為O(n)
Example
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest ...
求陣列中元素相加所能取得的最大值,這些元素必須相臨,複雜度為O(n)
- Example
Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.
- 解法
var maxSubArray = function(nums) { let max = nums[0]; let sum = 0; const len = nums.length; for(let i=0; i < len; i++){ //遍歷累加 sum += nums[i] //累加一次就和以前的最大值比較,並將最大值賦予給max,這樣max永遠都是最大值 if(sum > max){ max = sum } // 最關鍵的一步,當sum累加的值為負數,與下一個數累相加和只會變小 // 所以這個時候,讓sum=0,從下一個數開始從新累加,然後新累加的值,繼續和原來最大的max比較 if( sum < 0){ sum = 0; } } return max };
思考如果返回的是最大和的元素組成
var arr = [0,-3,-1,-23,9,99,-5,-5] var res = maxSubArray(arr) console.log(res) // [9,99] 解法: var maxSubArray = function(nums) { let max = nums[0]; let sum = 0; const len = nums.length; let start = 0; let end = 0; let e = 0; let s = 0; for(let i=0; i < len; i++){ sum += nums[i] if(sum >= max){ // 只要出現sum大於max,那麼最後一個值肯定就是sum[i] end = i + 1 start = s max = sum } if( sum < 0){ sum = 0; // 當sum為負數,有可能接下來的累加值會大於之前的最大max // 所以這裡的起點先儲存一個,後面如果累加大於前面的,起點從這裡算 // [1,2,-4,5,6]為例子: 當i為2的時候,sum = 1+2-4 =-1小於0 // 而接下來5+6會是最大值,起點是5所在的位置為i=3 s =i + 1 } } const arr = nums.slice(start,end ) return arr };