Question
给定一个整数数组，找出总和最大的连续数列，并返回总和。
Example 1:
输入： [-2,1,-3,4,-1,2,1,-5,4] 输出： 6 解释： 连续子数组 [4,-1,2,1]
的和最大，为 6。
进阶：
如果你已经实现复杂度为 O(n)
的解法，尝试使用更为精妙的分治法求解。
Approach 1: 动态规划
动态规划问题从这两方面思考：
- dp[i] 表示什么；
- dp[i] 怎么更新（状态转移方程）；
这里我用 dp[i] 表示前 i 个元素的子数组和的最大值，更新方式为：
注意上面的更新方式是有问题的，只考虑了从第一个元素开始建立子数组，没考虑从其他元素启始建立子数组，正确的更新方式应该是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def maxSubArray(self, nums) -> int:
n=len(nums)
dp = nums
for i in range(1,n):
dp[i] = max( nums[i], dp[i-1] + nums[i])
return max(dp)
def main():
nums = [-2,1,-3,4,-1,2,1,-5,4]
solution=Solution().maxSubArray(nums)
print(solution)
if __name__ == "__main__":
main()
|
复杂度分析
- 时间复杂度 O(N)： 线性遍历数组 nums
- 空间复杂度 O(N)： 需要建立dp
Approach 2: 滚动数组
方法1中需要建立一个长度为n的dp数组，使得空间复杂度为，实际上可以使用一个滚动数组的概念把空间复杂度降低到。即把dp[0 :
i-1]中最大的值赋值给一个变量，每次迭代都更新它，最后用这个变量输出结果。
1
2
3
4
5
6
7
| def maxSubArray1(self, nums) -> int:
dp = 0
maxA = nums[0]
for i in range(len(nums)):
dp = max( nums[i], dp + nums[i])
maxA = max( dp, maxA )
return maxA
|
复杂度分析
- 时间复杂度 O(N)： 线性遍历数组 nums
- 空间复杂度 O(1)： 需要建立常数个变量