【leetcode】53.最大子数组和

题目描述

题目思路

个人题解

暴力解法

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    let max = -Infinity;
    for (let i = 0; i < nums.length; i++) {
        let sum = 0;
        for (let j = i; j < nums.length; j++) {
            sum += nums[j];
            console.log(sum);
            if (sum > max) {
                max = sum;
            }
        }
    }
    return max;
};

“

超出时间限制

时间复杂度 1+2+3+4+...n (1+n)*n/2 所以是O(n^2) //其实一般N^2的都通过不了..

空间复杂度是O(1)

”

动态规划

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    const pre = [nums[0]]; 
    let maxAns = nums[0];
    for(let i = 1; i<nums.length; i++){
        pre[i] = Math.max(pre[i-1]+nums[i],nums[i]);
       // maxAns = Math.max(maxAns,pre[i]);
    }
    maxAns = Math.max(...pre);
    return maxAns;
};

时间复杂度O(n) 一个for循环

空间复杂度O(n) pre是个数组

优化后

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    let pre = nums[0];
    let maxAns = nums[0];
    for (let i = 1; i < nums.length; i++) {
        pre = Math.max(pre + nums[i], nums[i]);
        maxAns = Math.max(maxAns, pre);
    }
    return maxAns;
};

空间复杂度是O(1);

贪心算法

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function (nums) {
    //类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
    let result = -Infinity;
    let numsSize = nums.length;
    let sum = 0;
    for (let i = 0; i < numsSize; i++) {
        sum += nums[i];
        result = Math.max(result, sum);
        //如果sum < 0，重新开始找子序串
        if (sum < 0) {
            sum = 0;
        }
    }

    return result;
};

“

分而治之没有想到...

”

官方题解

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) => {
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    });
    return maxAns;
};

时间复杂度（time complexity）

O(n)

空间复杂度（space complexity）

O(1)