改进的关键在于求nFrom的算法。
    考虑到其中的状态转化方程：nFrom[i] = max{nFrom[i + 1] , max{Sum[i][k]  | i <= k && k < n}};如果要求出所有的Sum[i][k]再比较，必将产生O(n^2)的时间复杂度，而这是不允许的。
　　　如果换一种思路：为什么不直接将maxSum作为一个变量加以研究呢？事实上，如果令Smax[i] = max{Sum[i][k]  | i <= k && k < n}，那么考虑i-1的情况：
　　　Smax[i - 1] = max{Sum[i - 1][k] |  i -1<= k && k < n}
　　　          = max{Sum[i - 1][i -1],  max {Sum[i-1][k] | i <= k}}
　　　          =max{nArray[i-1][i-1], nArray[i-1][i-1] + Smax[i]};
　　　这样一来，问题就迎刃而解了……时间复杂度成功降至O(n)


Here's my Source Code:<C++ Memory: 1336 K  Time: 172ms>

#include<iostream>
using namespace std;

const int MAX = 50005;
const int MIN = -2147483647;
static int nArray[MAX] = {0};
//The biggest-sum sequence from a[i]/ to a[i]
static int nFrom[MAX] = {0},nTo[MAX] = {0};

int main(){
	int nCount,n,nTempMax,nMax;
	scanf("%d",&nCount);
	for(;nCount > 0;--nCount){
		scanf("%d",&n);
		nMax = MIN;
		for(int i = 0;i < n;++i){
			scanf("%d",&nArray[i]);
		}
		nTo[0] = nArray[0];
		nFrom[n - 1] = nArray[n - 1];

		/* Get the nTo[i] */
		nTempMax = nArray[0];
		for(int i = 1;i < n;++i){
			//The highest sum to i is max(highest[i-1],nTempMax(include i))  )
			nTempMax = nTempMax > 0 ? nTempMax + nArray[i] : nArray[i];
			nTo[i] = nTo[i-1] > nTempMax ? nTo[i-1] : nTempMax;
		}

		/* Get the nFrom[i] */
		nTempMax = nArray[n-1];
		for(int i = n - 2;i >= 0;--i){
			nTempMax = nTempMax > 0 ? nTempMax + nArray[i] : nArray[i];
			nFrom[i] = nFrom[i+1] > nTempMax ? nFrom[i+1] : nTempMax;
		}
		for(int i = 0;i < n - 1;++i){
			nMax = nTo[i] + nFrom[i+1] > nMax ? nTo[i] + nFrom[i+1] : nMax;
		}
		printf("%d\n",nMax);
	}
	return 0;
}