#53 Maximum Subarray (有圖)

先把問題切小然後再運算 (好題)

LeetCode

Given an integer array nums, 
find the contiguous subarray (containing at least one number) 
which has the largest sum and return its sum.

out: 找找看相鄰的哪些加起來最大

Example:

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

If you have figured out the O(n) solution, 
try coding another solution using the divide and conquer approach, 
which is more subtle.

Edge Case

• 只有一個就回傳那個值

• 會有負的喔

怎麼解

這題蠻值得思考的，我要鄰近數字加起來取 "最大值"，所以我可以自己跟前面比較取最大值

代表鄰近相加的總和，最後再取最大的，所以這個例子就是 6

var maxSubArray = function(nums) {
    if(nums.length < 2){
        return nums;
    }
    for(let i = 1; i < nums.length; i++){
        nums[i] = Math.max(nums[i], nums[i] + nums[i - 1])
    }
    return Math.max(...nums)
  

};
console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))

學到什麼?

答案要什麼很重要，是一個值而已還是 Array，這題只要最大值所以我們不用去管是哪幾個相加起來只要著重在相加最大值是什麼就好了