Shinkai005

V1

2022/02/12阅读:43主题:红绯

# 【leetcode】53.最大子数组和

【leetcode】53.最大子数组和

image-20220212085245101
image-20220212085245101

题目描述

image-20211222225344817
image-20211222225344817

题目思路

个人题解

暴力解法

/**
 * @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)

分类:

前端

标签:

JavaScript

作者介绍

Shinkai005
V1

公众号:深海笔记Shinkai