首页 > 代码库 > 动态规划——最大子串和

动态规划——最大子串和

如   {-4, 11,-2, 13,-7,-3,12} 的最大子段和为22

程序代码:

#include<iostream>  
#define MAXSIZE 100  
using namespace std;  
int MaxSum(int[],int);  
int main(void)  
{  
    int n;  
    int array[MAXSIZE];  
    while(cin>>n)  
    {  
        for(int i=1;i<=n;i++)  
        {  
            cin>>array[i];  
        }  
        cout<<MaxSum(array,n)<<endl;  
    }  
    return 0;  
}  
int MaxSum(int array[],int n)  
{  
    int b=0;  
    int sum=0;  
    for(int i=1;i<=n;i++)  
    {  
        if(b>0)  
        {  
            b+=array[i];  
        }  
        else  
        {  
            b=array[i];  
        }  
        if(b>sum)  
        {  
            sum=b;  
        }  
    }  
    return sum;  
}  

动态规划——最大子串和