最大子数组伪代码 c 动态规划

在C语言中，最大子数组问题通常使用动态规划方法解决，目的是找到给定整数数组中的连续子数组，使其元素之和最大。以下是求解这个问题的简单动态规划伪代码：

// 定义一个函数，输入数组arr和数组长度n
int maxSubArray(int arr[], int n) {
    // 初始化两个变量：当前最大和全局最大
    int currMax = arr[0];
    int globalMax = arr[0];

    // 使用动态规划循环，遍历整个数组
    for (int i = 1; i < n; i++) {
        // 如果当前元素加上前一个元素的最大和大于当前元素本身
        if (currMax + arr[i] > arr[i]) {
            // 更新当前最大值
            currMax += arr[i];
        } else {
            // 否则，从当前元素开始新的子数组
            currMax = arr[i];  // 当前最大和等于当前元素
        }

        // 比较当前最大值和全局最大值，更新后者
        if (globalMax < currMax)
            globalMax = currMax;
    }
    
    // 返回全局最大和
    return globalMax;
}

这个算法的核心思想是维护两个变量：`currMax`代表到当前位置为止的最长连续子数组的和，而`globalMax`则是所有子数组中的最大和。如果当前元素可以与之前的子数组合并增加和，则继续累加；否则，将`currMax`重置为当前元素。