題目來自nyist第44題，詳細如下

描述

對于每組測試數(shù)據(jù)輸出和最大的連續(xù)子串的和。

非常經(jīng)典的題目，而且網(wǎng)上也有很多DP集錦，寫來僅僅是為了自己能夠掌握。

大意是在一個整數(shù)串中尋找有最大和值的連續(xù)子串，初次見這種題似乎不太理解要做什么，既然這道題需要用動規(guī)來解，主要是要推出狀態(tài)轉(zhuǎn)移方程，也就是遞推公式類似an=f(an-1)這樣的形式。現(xiàn)在從頭開始推，這里使用兩個變量all和start來作為標記，all表示總體的最大和值，start表示第i個元素作為結束值（這里，如果是從后往前 推，則是作為開始值）的最大和值，i來自于for循環(huán)。

在for循環(huán)中的第i次執(zhí)行過程中，start[i] = max（start[i-1]+a[i],start[i-1]），start[i-1]相當于前i-1個數(shù)組成的序列中包含第i-1個數(shù)的最大和值，現(xiàn)在加入第i個數(shù)，這個start[i]要么只有他自己，要么就一定要包含第i-1個數(shù)并包含前若干個數(shù)，這若干個數(shù)在求start[i]時不可知，但是其值就是start[i-1]；同時all[i] = max（all[i-1],start[i]），即總體最大和要么是上一次求出的只含i-1個數(shù)（不含第i個數(shù)）的最大和，要么就是以第i個數(shù)作為結尾（包含第i個數(shù)）的最大和值。start和all的數(shù)組形式可以省略。

代碼如下：

#include <stdio.h>int a[1000000+5]; int main(){	int all,start,max,i;	int N,n;	scanf("%d",&N);	while(N--)	{		scanf("%d",&n);		for(i=0;i<n;i++)			scanf("%d",&(a[i])); 		all = start = a[0];		for(i=1;i<n;i++)		{			start = a[i] > (a[i]+start) ? a[i] : (a[i]+start);			all = start > all ? start : all; 		} 		PRintf("%d/n",all); 	} 	return 0;} 那么為什么會想到all和start呢？不同題目有不同的具體思路，現(xiàn)在我還不太能解釋，這也是從他人的解題思路中見到的。留下一個坑，當我有能力的時候再回來填。這只是一道基礎題目，當時可以窺見DP的重要思想。不過要真正掌握還需要勤加練習。
靈感方法來源于http://blog.csdn.net/songuooo/article/details/7843362（侵刪），這是從后往前推的方法，我這個代碼最多算是改寫了，因為個人感覺從前往后推習慣一些。