段树专题

POJ 2750 环上线段树 略带DP 的线段树

求一个环上的最大连续子列的和。但是这个区间不能是整个换。 做法: 把环拆开。 对于最大连续子列,有两种情况 第一种情况,子列在 1~n 中,这样便可以直接求出 第二种情况,子列既包括 1 又包括 n ,首先 最大列和最小列应该是不重合的(除非全是正数),如果重合,假设重合点是正数,则最小列可以更小,如果重合点是负数,则最大列可以更大,矛盾,然后,最大列和最小列应该全部覆盖整个环,证明和上