力扣第 53 题：最大子数组和

C 语言实现力扣第 53 题：最大子数组和的动态规划解法

题目分析

题目给定一个整数数组 nums，目标是找到和最大的连续子数组（最少包含一个元素），并返回其和。例如，在数组 [-2,1,-3,4,-1,2,1,-5,4] 中，和最大的子数组为 [4, -1, 2, 1]，其和为 6。

解题思路：动态规划法

动态规划 是一种通过将复杂问题分解成较小子问题来求解的优化方法。我们定义一个 currentSum 变量来记录当前的子数组和，定义 maxSum 来保存全局的最大子数组和。对于每个元素 nums[i]，我们需要做的是：

1. 选择更优的子数组和：currentSum = max(currentSum + nums[i], nums[i])
   • 如果前面的累加和 currentSum 为正数，则继续累加当前元素 nums[i]。
   • 如果 currentSum 为负，则丢弃它，从当前元素 nums[i] 重新开始新的子数组。
2. 更新全局最大子数组和：maxSum = max(maxSum, currentSum)

通过遍历数组，每次更新 maxSum，最终即可得到最大子数组和。

动态规划法的代码实现

以下是使用动态规划方法的 C 语言实现代码：

#include <stdio.h>

int maxSubArray(int* nums, int numsSize) {
    if (numsSize == 0) return 0;

    int maxSum = nums[0];  // 保存最大和，初始化为数组的第一个元素
    int currentSum = nums[0];  // 保存当前的子数组和，初始化为第一个元素

    for (int i = 1; i < numsSize; i++) {
        // 更新 currentSum，使其表示以 nums[i] 结尾的子数组的最大和
        currentSum = currentSum > 0 ? currentSum + nums[i] : nums[i];
        
        // 更新 maxSum，以保证它是最大的子数组和
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
    }

    return maxSum;
}

int main() {
    int nums[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int result = maxSubArray(nums, numsSize);
    printf("最大子数组和为: %d\n", result);  // 输出 6

    return 0;
}

逐行解释代码

1. 初始化最大和 maxSum 和当前子数组和 currentSum

    int maxSum = nums[0];
    int currentSum = nums[0];

• maxSum：保存最大子数组和，初始化为第一个元素的值，因为子数组至少包含一个元素。
• currentSum：保存当前以 nums[i] 结尾的子数组和，同样初始化为第一个元素。

2. 遍历数组并更新当前子数组和 currentSum

    for (int i = 1; i < numsSize; i++) {
        currentSum = currentSum > 0 ? currentSum + nums[i] : nums[i];

• 从数组的第二个元素开始遍历，逐步更新 currentSum。
• 状态转移方程：currentSum = max(currentSum + nums[i], nums[i])
  • 如果 currentSum 为正数，则继续累加 nums[i]。
  • 如果 currentSum 为负数，说明之前的累积和对最终结果没有贡献，从 nums[i] 重新开始子数组。

3. 更新全局最大和 maxSum

        if (currentSum > maxSum) {
            maxSum = currentSum;
        }

• 更新 maxSum，保证它始终为当前遍历过的子数组和的最大值。

4. 返回结果

    return maxSum;

• 遍历完成后，maxSum 即为所求的最大子数组和。

示例演示

以数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例，逐步查看 currentSum 和 maxSum 的变化：

i	nums[i]	currentSum	maxSum
0	-2	-2	-2
1	1	max(-2 + 1, 1) = 1	1
2	-3	max(1 - 3, -3) = -2	1
3	4	max(-2 + 4, 4) = 4	4
4	-1	max(4 - 1, -1) = 3	4
5	2	max(3 + 2, 2) = 5	5
6	1	max(5 + 1, 1) = 6	6
7	-5	max(6 - 5, -5) = 1	6
8	4	max(1 + 4, 4) = 5	6

最终结果 maxSum = 6，对应的子数组为 [4, -1, 2, 1]。

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组长度。只需遍历一次数组。
• 空间复杂度：O(1)，只使用了常数空间来保存 maxSum 和 currentSum。

原文地址：https://blog.csdn.net/weixin_48941116/article/details/143774147

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！