【DP入门】最大连续子串和

题目来自nyist第44题，详细如下

描述

对于每组测试数据输出和最大的连续子串的和。

非常经典的题目，而且网上也有很多DP集锦，写来仅仅是为了自己能够掌握。

大意是在一个整数串中寻找有最大和值的连续子串，初次见这种题似乎不太理解要做什么，既然这道题需要用动规来解，主要是要推出状态转移方程，也就是递推公式类似an=f(an-1)这样的形式。现在从头开始推，这里使用两个变量all和start来作为标记，all表示总体的最大和值，start表示第i个元素作为结束值（这里，如果是从后往前 推，则是作为开始值）的最大和值，i来自于for循环。

在for循环中的第i次执行过程中，start[i] = max（start[i-1]+a[i],start[i-1]），start[i-1]相当于前i-1个数组成的序列中包含第i-1个数的最大和值，现在加入第i个数，这个start[i]要么只有他自己，要么就一定要包含第i-1个数并包含前若干个数，这若干个数在求start[i]时不可知，但是其值就是start[i-1]；同时all[i] = max（all[i-1],start[i]），即总体最大和要么是上一次求出的只含i-1个数（不含第i个数）的最大和，要么就是以第i个数作为结尾（包含第i个数）的最大和值。start和all的数组形式可以省略。

代码如下：

#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呢？不同题目有不同的具体思路，现在我还不太能解释，这也是从他人的解题思路中见到的。留下一个坑，当我有能力的时候再回来填。这只是一道基础题目，当时可以窥见DP的重要思想。不过要真正掌握还需要勤加练习。
灵感方法来源于http://blog.csdn.net/songuooo/article/details/7843362（侵删），这是从后往前推的方法，我这个代码最多算是改写了，因为个人感觉从前往后推习惯一些。