一、题目描述：
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
二、思路分析：
动态规划
1.从数组第一个元素开始，分别累加数组的元素
2.当求和到当前元素为负数和时，重新计算下一轮数组和，并记录当前的最大和
3.比较每轮数组和，返回最大值；
三、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.动态求和，动态更新最大记录。继续加油！
