我还没有写针对N<=10^5的算法，只是针对<=1000把这道题过了，真正要搞<=10^5要花不少时间，难度不在一个数量及上，我只是有了点初步的想法，实际效果还没有试：


首先这道题是  O(n^2)状态，多种记录方式: 可以用[i][j]表示前i个项目合并成了j
块的最大正负差。
现在想到的有两个优化：
1.状态转移：方程是dp[i][j]=max(dp[s][j-1])+w[s][i]  可以对[j-1]建立一个表用
某种数据结构记录比如set,因为w[s][i]只能取1和-1，所以只需要去表中的最大值max,
以及max-1 就行了，其它的值全部减掉，这样转移的复杂度就是O(1)

2.状态的优化(或者说状态的剪枝)：就是我前面说的上下界剪枝， 以当前状态的代价
+到终点的上界估价来更新答案，然后 所有的状态如果+到终点的下界>=ans这个状态就废了，减掉。

利用优化2  可以将O(N^2)的状态减成不到N^2，当然不能直接用数组记录 dp[i][j],具体实现可以选择set...

现在1 的优化是确定的，转移的复杂度基本就是O(1),关键是优化2，大致测了一下我
AC代码的估价函数  已经把总的有用状态减到了 (1/4~1/5) *N^2(测了几组 1000的和100的数据)。。 这个方法搞10^5数据量还远远不够...

现在想到进一步优化 估价函数的方法，具体效果还需要尝试。。。。