任务描述 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 测试说明 输入的第一行是一个整数 N, 代表数组的大小 输入的第二行是 N 个整数 用c++

语实现一个函数 int maxSubArray(int* nums, int numsSize) ，其中 nums 表示输入的整数数组，numsSize 表示数组的大小，函数需要返回最大的连续子数组的和。

示例 输入: 6 -2 1 -3 4 -1 2 输出: 6 解释: 连续子数组 [4,-1,2] 的和最大，为 6。

提示： 要求时间复杂度为 O(n)。

相关问题

任务描述 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。输入的第一行是一个整数 N, 代表数组的大小 输入的第二行是 N 个整数

，表示数组中的元素。输出一个整数，表示最大子数组的和。

示例输入：

6
-2 1 -3 4 -1 2

示例输出：

6

示例说明：

连续子数组 [4,-1,2] 的和最大，为 6。

提示：

1 <= N <= 10^5
-10^4 <= nums[i] <= 10^4

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

思路：动态规划

1. 定义状态：dp[i]表示以第i个数结尾的最大子数组和

2. 状态转移方程：dp[i] = max(nums[i], dp[i-1]+nums[i])

3. 初始状态：dp[0] = nums[0]

4. 最终结果：遍历dp数组，求出最大值即可

Python代码：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        for i in range(1, n):
            dp[i] = max(nums[i], dp[i-1]+nums[i])
        return max(dp)

时间复杂度：O(n)

空间复杂度：O(n)