最大连续子序列之和
今天在做数据结构的一道编程题时，看到了这个求最大连续子序列之和的问题。即给你一个不全为负的整型数组，求这个数组的最大连续子序列之和。这也是一个很经典的问题。算法有很多种，比如，穷竭搜索，还有分治法。穷竭搜索的时间复杂度为O(n³)，分治法的时间复杂度为O(nlogn)。其实还有一种更高效的算法：动态规划，时间复杂度为O(n)，是一个线性算法。
Code :
/*
*求最大连续子序列之和
*动态规划：时间复杂度O(n)
*author: Jorbe
*date: 2013.12.11
*/
//输入
int n;
int A[n];
int solve()
{
int max_sum=0,tmp_sum=0;
for(int i=0;i<n;i++)
{
tmp_sum+=A[i];
if(tmp_sum>max_sum)
max_sum=tmp_sum;
if(tmp_sum<0)
tmp_sum=0;
}
return max_sum;
}