在 P1115 最大子段和 用线段树实现 O(n) 的分治做法后，我决定用 DP 解决本题。

DP 方程如下：

 									     0  a[i] INF  
(0,dp[i+1],ans[i+1])=(0,dp[i],ans[i])*( INF a[i]  0  )  
									    INF  INF  0	  

思路与 P1115 大致相同，只是要多一位 ans 统计答案（前面的 DP 值的最大者），所以可以用动态 DP 方法解决此题。
不过如果使用优化过的矩阵，转移方程就和普通的线段树维护操作一样了。

由此不难得知此题可以有树上版本，好像只从线段树维护区间也可以看出来， 不知道洛谷上面有没有这样的题？