力扣 53. 最大子数组和（C语言+分治递归、动态规划）

1. 题目

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

2. 输入输出样例

        示例 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

3. 解题思想

（1）分治递归

        分治法的核心部分。一个整数数组 nums，以及左边界 l 和右边界 r。通过递归的方式将数组划分成更小的子数组，分别找到左半部分、右半部分以及跨越中间位置的子数组的最大和。具体步骤如下：

• 当左边界等于右边界时，表示只有一个元素，直接返回该元素作为最大子数组和。
• 计算中间位置，将数组分成左半部分和右半部分。
• 分别递归调用来找到左半部分和右半部分的最大子数组和。
• 计算跨越中间位置的最大子数组和，通过两个循环分别向左和向右遍历，找到最大的左半部分和最大的右半部分。
• 最后，通过比较左半部分、右半部分和跨越中间的子数组和，返回其中的最大值。

（2）动态规划

         动态规划算法通过迭代遍历输入数组，维护一个额外的数组 dp 来记录截止到每个位置的最大连续子数组和，并利用一个变量 max_num 实时更新全局最大子数组和的值。

        算法的核心思想在于，通过比较当前元素和前一个元素的最大子数组和是否大于零，来决定是否将当前元素加入前一个子数组或者从当前元素重新开始形成子数组。最终，返回 max_num 作为最大子数组和的解。

• 初始化dp：dp[i]表示前i个元素最大的连续子数组和
• 状态转移：如果dp[i-1] > 0, dp[i] = dp[i-1] + nums[i],否则dp[i] = nums[i](分类讨论)
• 初始换状态：dp[0] = nums[0]
• 最优解：max(dp)

开始

初始化：
- 数组 dp，大小为 numsSize，用于存储前 i 个元素的最大连续子数组和
- 变量 max_num，用于记录全局最大子数组和
- 将 dp[0] 设置为 nums[0]
- 将 max_num 设置为 nums[0]

遍历数组：
对于 i 从 1 到 numsSize-1：
    如果 dp[i-1] 大于 0：
        - 更新 dp[i] 为 dp[i-1] + nums[i]
    否则：
        - 更新 dp[i] 为 nums[i]
    
    更新 max_num 为 dp[i] 和 max_num 之间的较大值

结束

返回 max_num 作为最大子数组和的解

4. 代码实现

（1）分治递归

// 求三个整数中的最大值
int maxz(int a, int b, int c) {
    // 注意这里等于时的判断
    if (a >= b && a >= c) {
        return a;
    }
    if (b >= a && b >= c) {
        return b;
    }
    return c;
}

// 使用分治法来找到最大子数组和
int maxarry(int* nums, int l, int r) {
    // 当只有一个元素时，直接返回该元素
    if (l == r) {
        return nums[l];
    } 
    // 划分数组的中间位置
    int mid = (l + r) / 2;
    // 分别找到左半部分和右半部分的最大子数组和
    int maxl = maxarry(nums, l, mid);
    int maxr = maxarry(nums, mid + 1, r);
    
    // 计算跨越中间位置的最大子数组和
    int i = mid - 1, j = mid, addl = 0, addr = 0, max1 = 0, max2 = nums[mid];
    for (; i >= l; i--) {
        addl += nums[i];
        if (addl > max1) {
            max1 = addl;
        }
    }
    for (; j <= r; j++) {
        addr += nums[j];
        if (addr > max2) {
            max2 = addr;
        }
    }
    int maxm = max1 + max2;
    // 返回左半部分、右半部分和跨越中间的最大子数组和中的最大值
    return maxz(maxl, maxr, maxm);
}

// 主函数，用于调用 maxarry 函数来解决最大子数组和问题
int maxSubArray(int* nums, int numsSize) {
    // 分治法求解最大子数组和
    return maxarry(nums, 0, numsSize - 1);
}

（2）动态规划

// 定义一个函数，用于返回两个整数中的较大值
int max_(int a, int b) {
    if (a <= b) {
        return b;
    }
    return a;
}

// 使用动态规划解决最大子数组和问题
int maxSubArray(int* nums, int numsSize) {
    // 如果数组只有一个元素，直接返回该元素
    if (numsSize == 1) {
        return nums[0];
    }
    
    int n = numsSize;
    
    // 初始化一个数组 dp，dp[i] 表示前 i 个元素的最大连续子数组和
    int dp[n];
    dp[0] = nums[0];
    
    // 初始化最大子数组和为第一个元素
    int max_num = nums[0];
    
    // 开始状态转移
    for (int i = 1; i < n; i++) {
        // 如果 dp[i-1] 大于 0，则更新 dp[i] 为 dp[i-1] + nums[i]
        // 否则，从当前位置重新开始计算子数组和，即 dp[i] = nums[i]
        if (dp[i - 1] > 0) {
            dp[i] = dp[i - 1] + nums[i];
        } else {
            dp[i] = nums[i];
        }
        
        // 更新最大子数组和
        max_num = max_(max_num, dp[i]);
    }

    // 返回最大子数组和
    return max_num;
}

5. 复杂度分析

（1）分治递归

1. 时间复杂度分析：

2. maxz 函数的时间复杂度是 O(1)，因为它只执行了一系列常数时间的比较操作。

3. maxarry 函数是递归的，每次将数组分成两半，然后再合并结果。递归树的高度为 log₂(n)，其中 n 是输入数组的大小。在每个递归层级，我们都要遍历一次数组来计算跨越中间位置的最大子数组和，这需要 O(n) 的时间。因此，maxarry 函数的总时间复杂度为 O(n log₂(n))。

总的时间复杂度是 maxarry 函数的时间复杂度，即 O(n log₂(n))。

• maxSubArray 函数中的循环遍历整个数组一次，需要 O(n) 的时间。

空间复杂度分析：

1. maxz 函数的空间复杂度是 O(1)，因为它没有使用额外的数据结构。

2. maxarry 函数中的递归调用会使用一些额外的栈空间，但这个空间占用是由递归树的深度决定的，最坏情况下为 O(log₂(n))。

3. maxarry 函数中使用了一个额外的数组 dp，其大小与输入数组相同，因此空间复杂度为 O(n)。

4. maxSubArray 函数中的额外空间只包括了几个整数变量，因此空间复杂度是 O(1)。

        综合考虑时间和空间复杂度，时间复杂度是 O(n log₂(n))，空间复杂度是 O(n)。 

（2）动态规划

时间复杂度分析：

1. 初始化 dp 数组需要 O(n) 的时间，其中 n 是输入数组的大小。

2. 循环遍历输入数组一次，从第二个元素开始进行状态转移，每个元素的状态转移操作都需要 O(1) 的时间。因此，状态转移的时间复杂度是 O(n)。

总的时间复杂度是初始化时间和状态转移时间的总和，即 O(n) + O(n) = O(n)。

空间复杂度分析：

1. 需要一个额外的整数数组 dp 来存储前 i 个元素的最大连续子数组和，这个数组的大小与输入数组相同，因此空间复杂度为 O(n)。

2. 需要几个整数变量来维护当前最大子数组和，这些变量的空间占用是常数级别的，因此可以忽略不计。

总的空间复杂度主要由 dp 数组的空间占用决定，为 O(n)。

        综上所述，动态规划算法的时间复杂度是 O(n)，空间复杂度也是 O(n)。它具有线性时间复杂度，适用于解决最大子数组和问题，并且需要额外的线性空间来存储中间结果。

53. 最大子数组和 – 力扣（LeetCode）https://leetcode.cn/problems/maximum-subarray/