一、题目形容：

输出一个整型数组，数组中的一个或间断多个整数组成一个子数组。求所有子数组的和的最大值。
要求工夫复杂度为O(n)。

二、思路剖析：

动静布局

1.从数组第一个元素开始，别离累加数组的元素<br/>
2.当求和到以后元素为正数和时，从新计算下一轮数组和，并记录以后的最大和<br/>
3.比拟每轮数组和，返回最大值；<br/>

三、AC 代码：

javascript

/** * @param {number[]} nums * @return {number} */var maxSubArray = function (nums) {    //数组长度为1时，返回数组第一个元素    if(nums.length===1) return nums[0]    let dp = nums[0], max = nums[0]    for (let i = 1; i < nums.length; i++) {        //当和小于0时，抛弃这个后果，以后元素从新开始求和        dp = dp > 0 ? dp + nums[i] : nums[i]        //将之前计算的和，求出最大值        max = Math.max(dp, max)    }    return max};

Python

class Solution(object):    def maxSubArray(self, nums):        """        :type nums: List[int]        :rtype: int        """        if(len(nums)==1):            return nums[0]        dp,ret = nums[0],nums[0]        for i in range(1,len(nums)):            if dp>0:                dp = dp+nums[i]            else:                dp = nums[i]            ret = max(dp,ret)        return ret

Typescript

function maxSubArray(nums: number[]): number {    //数组长度为1时，返回数组第一个元素    if (nums.length === 1) return nums[0]    let temp:number= nums[0], max:number = nums[0]    for (let i = 1; i < nums.length; i++) {        //当和小于0时，抛弃这个后果，以后元素从新开始求和        temp = temp > 0 ? temp + nums[i] : nums[i]        //将之前计算的和，求出最大值        max = Math.max(temp, max)    }    return max};

Go

func maxSubArray(nums []int) int {    res:=nums[0]    for i:=1;i<len(nums) ;i++  {        //求和，小于0时，和等于0，从新求和        nums[i]+=max(nums[i-1],0)        //更新最大记录值        res=max(res,nums[i])    }    return res}//因为go语言外面没有max()函数，本人构建一个func max(a,b int) int{    if a>b{        return a    }    return b}

四、总结：

1.动静求和，动静更新最大记录。持续加油！