HDU 1024 - Max Sum Plus Plus
Problem : Given a sequence, find m non-overlap consequtive subsequence s.t. the sum of them is maximum.
Solution :
1) If S[i1..j1], S[i2..j2], ..., S[ik..jk] is maximum k non-overlap consequtive subsequence. k+1 non-overlap consequtive subsequence is above solution plus one non-chosen consequtive subsequence, or cut one of the chosen consequtive subsequence to two. (The proof can be found in the note). With this theory, with priority queue, the answer can be found in O(MlogM) time.

2) To find the maximum/minimum consequtive subsequence in given interval, using segment tree can archieve O(nlogn) init time and O(logn) query time. (See the note for detail). However, it's need O(n) space. This problem don't have enough space. Thus I use O(n) time query instead.

With both optimization above, the total time complexity is O(nlogn). Without the second optimization, the time complexity is O(NM).