连续子数组的最大和

问题描述：

输入一个整型数组，数组里有正数也有负数。求连续子数组中的最大和为多少。

举例：

数组：arry={1 , 2 ，-5 , 4 , 1 ，-2}

输出：5，数组中连续的位置相加最大值为5, 4+1

方法：

设立一个dp数组存储当前最大和状态。初始时将数组对应数字填入dp中。然后从头开始遍历dp，如果前一位dp[i]中保存的数大于0，则更新当前的dp值。更新结果是当前dp的值加上前一个dp的值。

代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<math.h>
int main() {
    int data[81], dp[81];
    int i, num, max = 0;
    printf("please input num:\n");
    scanf("%d", &num);
    printf("please input data:\n");
    for (i = 0; i < num; i++) {
        scanf("%d", &data[i]);
    }
    for (i = 0; i < num; i++) {//将data的数据复制到dp中
        dp[i] = data[i];
    }
    for (i = 1; i < num; i++) {
        if (dp[i - 1] > 0) {//如果dp前一个位置的值大于0，则与当前位置相加，更新当前位置的值
            dp[i] = dp[i] + dp[i - 1];
        }
    }
    for (i = 0; i < num; i++) {
        if (max < dp[i]) {
            max = dp[i];
        }
    }
    printf("the maximum sum of continuous subarrays is %d\n", max);
    return 0;
}

运行结果截图：