前言

大三上学期准备转行，可我一直到下学期才开始刷算法，以及准备软件方面的竞赛。在学习过程中，我能明显的感受到和其他人的差距，可能是题目做少了吧。。。所以今天开始第一篇刷题打卡！

一、题目描述：

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
难度：简单

示例1

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]<br>
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6.

示例 2：

输入：nums = [1]
输出：1

提示：

1 <= nums.length <= 3 * 10^4
-10^5 <= nums[i] <= 10^5

二、思路分析：

可能有部分人看到子序列就已经开始迷惑了，什么是子序列呢?

这里举一个栗子，设一个数列为 -6,-4,3,7,8,10。

在这个序列中，取连续的元素，重新组成一个序列，即子序列，例如-4，3，7,8,10等,子序列也可为空，如果序列的整数全部为负数的话，它的最大子序列为0。所以这个题目的意思即为，求这些子序列相加和的最大值。
首先我想到的方法是穷举法，即考虑全部的情况，并利用for循环将他们全部遍历，但这个方法的时间复杂度为O(n^3)，实在过大，而且超出时间限制，所以舍弃，采用另一种方法：动态规划法。我们通常的思维方法是先从数列的首个元素开始遍历，然后第二个，第三个...可动态规划不一样，它是以子序列的结束点为基准，当在某个位置的序列值小于下一个元素时，直接从下一个元素开始遍历，计算最大的遍历值。

• 按照题目要求，当数组的长度为1时，返回数组里面的值，其实当数组里面只有一个数组时，最大序列值应该为0。

if (!nums.length) {
        return nums[0];
    };

• 设置最后的结束点，以及最初序列长度的值

let max_ending_here = nums[0];
    let max = nums[0];

• 从第二位元素开始遍历，如果第一位开始遍历的序列值小于下一个元素值，则从下一位元素开始遍历，找到最终的最大值

 for (let i = 1; i < nums.length; i ++ ) {
   
        max_ending_here = Math.max ( nums[i], max_ending_here + nums[i]);
        max = Math.max ( max, max_ending_here);
    };

三、AC 代码：

function  maxSubArray2  ( nums ) {
// 按照题目要求，如果只有一个元素，元素的值即最大序列值
    if (!nums.length) {
        return nums[0];
    };
    
    let max_ending_here = nums[0];
    let max = nums[0];

    for (let i = 1; i < nums.length; i ++ ) {
        // 遍历

        max_ending_here = Math.max ( nums[i], max_ending_here + nums[i]);
        max = Math.max ( max, max_ending_here);
    };

    return max;
};

四、总结：

刚开始刷算法我总是习惯性的开始for循环...但是随着学习的深入，很快就会发现穷举法的局限性很大，暴力解法非常占用内存，所以，还是多多学习算法吧...

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情