题目链接： 最大子数组和

有关题目

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），
返回其最大和。子数组 是数组中的一个连续部分。

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

示例 2：输入：nums = [1]
输出：1

示例 3：输入：nums = [5,4,-1,7,8]
输出：23

提示：1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

题解

法一：动态规划

#define MAX(a, b) ((a) > (b) ? (a) : (b))int maxSubArray(int* nums, int numsSize){int i;   int dp[numsSize];//dp[i] 表示以nums[i]结尾最大子数组和int ans = nums[0];dp[0] = nums[0];//初始状态for (i = 1; i < numsSize; i++){dp[i] = MAX(dp[i - 1] + nums[i], nums[i]);//转移方程ans = MAX(dp[i], ans);}return ans;
}

时间复杂度：O(n)
空间复杂度：O(n)

法二：滚动数组
参考官方题解

#define MAX(a, b) ((a) > (b) ? (a) : (b))int maxSubArray(int* nums, int numsSize){int i;int pre = nums[0], ans = nums[0];//pre记录为i之前最大子数组和for (i = 1; i < numsSize; i++){//当前 pre 作为下一次循环进来的 最大子数组之和pre = MAX(pre + nums[i], nums[i]);ans = MAX(ans, pre);}return ans;
}

时间复杂度：O(n)
空间复杂度：O(1)