动态规划：最大子区间之和

问题描述

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

子数组 是数组中的一个连续部分。

例如：

输入： $nums = [-2,1,-3,4,-1,2,1,-5,4]$

输出： $6$

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

思路

本题可用动态规划法解决。由题意写出动态规划的转移方程： 假设 $dp[i]$ 表示以第 $i$ 个元素结尾的连续子数组的最大和。则有以下转移方程：

$$dp[i] = max(nums[i], dp[i-1] + nums[i])$$

其中，$nums[i]$ 表示第 $i$ 个元素的值，$dp[i-1]$ 表示以第 $i-1$ 个元素结尾的连续子数组的最大和。

所以，算法用自然语言描述如下：

1. 定义一个数组 dp，长度与 nums 相同，用于存储以每个元素结尾的连续子数组的最大和。
2. 初始化 dp[0] = nums[0]，表示以第一个元素结尾的连续子数组的最大和为第一个元素的值。
3. 从第二个元素开始遍历数组 nums，对于每个元素 nums[i]，计算 dp[i] 的值：
   • 如果 dp[i-1] 大于 0，则 dp[i] = dp[i-1] + nums[i]，表示将当前元素加入到以第 i-1 个元素结尾的连续子数组中，可以得到更大的和。
   • 否则，dp[i] = nums[i]，表示当前元素自成一个连续子数组，其和为当前元素的值。
4. 遍历完整个数组后，找出 dp 中的最大值，即为所求的最大和。

代码实现：

int maxSubArray(int* nums, int numsSize) {
    int* dp = (int*)malloc(sizeof(int) * numsSize);
    dp[0] = nums[0];
    int maxSum = dp[0];

    for (int i = 1; i < numsSize; i++) {
        dp[i] = nums[i] > dp[i-1] + nums[i] ? nums[i] : dp[i-1] + nums[i];
        maxSum = dp[i] > maxSum ? dp[i] : maxSum;
    }

    free(dp);
    return maxSum;
}