0053. 最大子数组和 #
- 标签:数组、分治算法、动态规划
- 难度:简单
题目大意 #
给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
解题思路 #
动态规划的方法,关键点是要找到状态转移方程。
假设 f(i) 表示第 i 个数结尾的「连续子数组的最大和」,那么 $max_{0 < i \le n-1} {f(i)} = max(f(i-1) + nums[i], nums[i])$
即将之前累加和加上当前值与当前值做比较, 如果将之前累加和加上当前值 > 当前值,那么加上当前值;如果将之前累加和加上当前值 < 当前值,那么 $f(i) = nums[i]$。
代码 #
|
|