这个题有非常多O(n2)的算法。这里说一种：枚举每个区间，在枚举区间的同一时候维护区间内的最小值和区间和，将最小值与P的大小进行比較，贪心地取最大值就可以。注意若枚举到的区间是整个数组，则P的值是必须取的。
当然也存在O(n)的做法：从左往右处理出dp1[i]=max(a[i],dp1[i−1]+a[i]),相同从右往左处理出dp2[i]=max(a[i],dp2[i+1]+a[i])。再枚举要改动哪一个数，用两个数组更新答案就可以。

我是用了两次dp。事实上能够合成一个的，o(n2）的也是，每改一次dp一次，写的略丑。

}

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5307023.html，如需转载请自行联系原作者