动态规划——求最大子串和

输入一个整数n代表有几个数据，接着输入n个数据，求这n个数据组成的串中，子串和最大；

一道求最优解的动态规划问题。

dp[ i ] 表示与第i个数组合时，所能得到的最大值 ；

第n个数据（dp[ n ]）有两种年可能：1、当 dp[n-1] < 0 时 ，自己独立成为一个长度为1的子串 ( dp[ n ] = a[n] ) ;

   2、当 dp[n-1] >= 0 时 ，和dp[n-1]相加   (dp[n] = dp[ n-1 ] + a[ n ] ) ;

注意：dp[n] 不代表前n个数据中最大子串和，只代表与第n个数组合时，所能得到的最大值。

#include<iostream>
using namespace std ;
int main()  {
    int n ;
    cin >> n ;
    int a[100] ;
    int i = 1 ;
    int m = -1000000;
    for(; i <= n ; i++)
        cin >> a[i] ;
    int dp[100] = {0} ;
    for(int j = 1 ; j <= n ; j++)   {
        if( dp[j-1] < 0 )
            dp[j] = a[j] ;
        else
            dp[j] = dp[j-1] + a[j] ;
             m = max(m,dp[j]);
    }
    cout << m << endl ;
    return 0 ;
}

动态规划——求最大子串和,布布扣,bubuko.com

动态规划——求最大子串和

原文：http://blog.csdn.net/ding_hai_long/article/details/20998103