一、题目形容:
输出一个整型数组,数组中的一个或间断多个整数组成一个子数组。求所有子数组的和的最大值。
要求工夫复杂度为 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. 动静求和,动静更新最大记录。持续加油!