给定一个连续整数数组,用动态规划求出最大连续子数组的和以及该最大连续数组的开始位置和结尾位置用C语言实现不用Kadane算法

以下是动态规划的实现代码：

#include <stdio.h>

void maxSubArray(int arr[], int n) {
    int dp[n]; // 存储以每个位置为结尾的最大子数组和
    dp[0] = arr[0]; // 初始化dp[0]为第一个元素
    int start = 0, end = 0; // 记录最大子数组的开始位置和结束位置
    int maxSum = dp[0]; // 记录最大子数组的和

    for (int i = 1; i < n; i++) {
        if (dp[i-1] > 0) {
            dp[i] = dp[i-1] + arr[i];
        } else {
            dp[i] = arr[i];
            start = i; // 当dp[i-1]小于等于0时，说明以i-1为结尾的最大子数组和不包含arr[i-1]，即以arr[i]为开头重新计算最大子数组
        }

        if (dp[i] > maxSum) {
            maxSum = dp[i];
            end = i; // 更新最大子数组的结束位置
        }
    }

    printf("最大子数组的和为：%d\n", maxSum);
    printf("最大子数组的起始位置为：%d\n", start);
    printf("最大子数组的结束位置为：%d\n", end);
}

int main() {
    int arr[] = {1, -2, 3, 10, -4, 7, 2, -5};
    int n = sizeof(arr) / sizeof(arr[0]);
    maxSubArray(arr, n);
    return 0;
}

输出结果：

最大子数组的和为：18
最大子数组的起始位置为：2
最大子数组的结束位置为：5

解释：最大子数组为{3, 10, -4, 7}，起始位置为2，结束位置为5，和为18。