Leetcode#53 最大子序和

1.题目叙述

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

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

2.题目分析

之前有段时间想转码来着，所以稍微看过小一点数据结构，当时好像有看到这道题，给了很多解法，有 O ( n 2 ) O(n^2) O(n2)的暴力循环，也有 O ( n l o g n ) O(nlogn) O(nlogn)的二分法，最后给出的动态规划的解法复杂度仅为 O ( n ) O(n) O(n)，令我印象深刻。

3.具体代码

var maxSubArray = function(nums) {
//动态规划的问题
sums=nums[0];
sums1=nums[0];
for(let i=1;i<nums.length;i++)
{
if (sums<0)
{
    sums=nums[i];
}else
{
    sums=sums+nums[i];
}
if(sums>sums1)
{
    sums1=sums;
}

}

return sums1;
};

4.总结反思

这道题是见过的，方法也是知道的，但是真的是很不熟练，具体操作细节磨了好久，属于是面向bug的编程了。最深的感触是，每次有bug都是只修补bug的那一点，而拆了东墙补西墙。以后刷题要注意规划，要先从顶层架构着手，在心里跑一遍，再具体根据bug的特点修改，不要走重复的路线。

5.他山之石

var maxSubArray = function(nums) {
    let max = nums[0];
    let tmp = 0;
    for(let i=0;i<nums.length;i++){
        tmp = Math.max(tmp+nums[i],nums[i]);
        max = Math.max(max,tmp);
    }
    return max;
};

我深刻体会到，调用高级语言固有函数的优越性，但是奈何是初学者，就先暴力就完事了。