leecode 724
时间: 2023-07-29 10:10:46 浏览: 69
题目描述:
给定一个长度为 n 的整数数组 nums,其中 n > 0,求非空连续子数组的最大和。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
示例2:
输入: nums = [1]
输出: 1
示例3:
输入: nums = [0]
输出: 0
示例4:
输入: nums = [-1]
输出: -1
示例5:
输入: nums = [-100000]
输出: -100000
解法:
这道题可以使用动态规划来解决,具体做法如下:
设 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和。
则状态转移方程为:dp[i] = max(dp[i-1]+nums[i], nums[i])
其中,dp[i-1]+nums[i] 表示将 nums[i] 加入到以 nums[i-1] 结尾的连续子数组中,nums[i] 表示以 nums[i] 为起点重新开始一个连续子数组。
最终的答案为:max(dp[0], dp[1], ..., dp[n-1])
代码实现如下:
```python
def maxSubArray(nums):
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
dp[i] = max(dp[i-1]+nums[i], nums[i])
return max(dp)
```
时间复杂度为 O(n),空间复杂度为 O(n)。