53.Maximum Subarray.md

​

53. Maximum Subarray

Easy

https://leetcode.com/problems/maximum-subarray/

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

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.

思路

这道题求解连续最大子序列和

暴力解法：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    if(!nums || nums.length == 0) return 0
    if(nums.length == 1) return nums[0]
    let len = nums.length
    let maxSum = undefined
    let sum = 0
    for(let i = 0; i < len; i ++) {
        sum = 0
        for(let j = i; j < len; j ++) {
            sum += nums[j]
            if(maxSum == undefined) {
                maxSum = sum
            } else {
                maxSum = Math.max(maxSum, sum)
            }
        }
    }
    return maxSum
};