打卡13：leetcode53. 最大子序和｜刷题打卡

掘金团队号上线，助你 Offer 临门！ 点击 查看详情 (opens new window)

前言

第一次参加掘金打卡活动，别的不说 主要是奔着奖励来的。4.12开始为了达到14题小目标 冲冲冲！！！这是第13题。

题目描述

题目链接：最大子序和 (opens new window)

题目描述我用截图leetcode的为主，所以题目如下图

思路分析

这道题题末提示尝试使用更为精妙的 分治法 求解说明采用分治法是不错的解题思路，顺手搜了一下分治法的概念：

看完好的，还是没有很好的解题思路。那就按自己比较笨的方法实现吧。 思路：因为是连续数组组成的和，那我可以先遍历得到一组以自己本身为起点的最大值(从下标0开始到结束,最后一个可以直接输出本身),然后再求出这个数组的最大值，思路很容易理解 至于会不会超时要验证一下。

写完检查一下感觉逻辑没问题 点击提交 一直在loading我还以为会超时，好的最后还是成功了 但是这个耗时和内存消耗不敢恭维，确实是最差的方法了

那思路不变的情况下去优化看看，最后是存进一个数组然后再去取值这里太浪费内存，所以改成一个数，然后每次取到total去对比并记录max值，运行如下：

可以发现内存消耗上提升了很多，现在的问题是优化时间了，现在时间复杂度是O(n²),我需要思考思考。

AC 代码

/**
 * @param {number[]} nums
 * @return {number}
 */
 // 1
var maxSubArray = function(nums) {
    if(nums.length===1){
        return nums[0]
    }
    let maxArr = []
    for(let i=0;i<nums.length;i++){
        let total=nums[i]
        let total2 = 0
        for(let j = i;j<nums.length;j++){
            total2+=nums[j]
            if(total<total2){
                total=total2
            }
        }
        maxArr.push(total)
    }
    return Math.max(...maxArr)
};

// 2
var maxSubArray = function(nums) {
    if(nums.length===1){
        return nums[0]
    }
    let max = nums[0]
    for(let i=0;i<nums.length;i++){
        let total=nums[i]
        let total2 = 0
        for(let j = i;j<nums.length;j++){
            total2+=nums[j]
            if(total<total2){
                total=total2
            }
        }
        if(total>max){
            max=total
        }
    }
    return max
};

总结

坚持就是胜利。第13题算法完成，坚持就是胜利！！！

       ↓↓↓

→ 算法系列链接 (opens new window) ←

       ↑↑↑

这里可以点！这里可以点！这里可以点！