顺序表应用8：最大子段和之动态规划法

╰半橙微兮° 2023-03-02 13:26 21阅读 0赞

## 顺序表应用8：最大子段和之动态规划法 ##

Problem Description  
给定n(1<=n<=100000)个整数（可能为负数）组成的序列a\[1\],a\[2\],a\[3\],…,a\[n\],求该序列如a\[i\]+a\[i+1\]+…+a\[j\]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max\{0,a\[i\]+a\[i+1\]+…+a\[j\]\},1<=i<=j<=n。 例如，当（a\[1\],a\[2\],a\[3\],a\[4\],a\[5\],a\[6\]）=(-2,11,-4,13,-5,-2)时，最大子段和为20。

注意：本题目要求用动态规划法求解，只需要输出最大子段和的值。

Input  
第一行输入整数n(1<=n<=100000)，表示整数序列中的数据元素个数；

第二行依次输入n个整数，对应顺序表中存放的每个数据元素值。

Output  
输出所求的最大子段和

Sample Input  
6  
\-2 11 -4 13 -5 -2  
Sample Output  
20

#include <stdio.h>
    #include <stdlib.h>
    int main()
    {
        
    	int a[50010], i, n, sum = 0, max = 0;
    	scanf("%d", &n);
    	for (i = 0; i < n; i++)
    	{
        
    		scanf("%d", &a[i]);
    	}
    	for (i = 0; i < n; i++)/*动态规划，从头开始遍历，依次累计“和”，如果“和”加上该次的数据大于零，那么就把这个数据算在和里（最大和序列），
    						   如果“和”加上该次的数据小于零，负数sum定义为零，再从接下来的数据依次按照这种方法操作*/
    	{
        
    		if (sum + a[i] > 0)
    		{
        
    			sum = sum + a[i];
    			if (sum > max)
    			{
        
    				max = sum;
    			}
    		}
    		else
    		{
        
    			sum = 0;
    		}
    	}
    	printf("%d", max);
    }