Hi, everyone!
Do you remember the Max-Sum Subsequence? I don't know the exact name, but the problem is: Given an array of N elements, find the subsequence [i, j] such that the sum (a[i] + a[i+1] + a[...] + a[j]) maximizes.
And the problem I am working on (in vain), is given K queries, each is either to update (change value of) an element a[i] for some i (given in the query) or to find the Max-Sum subsequence [i, j] within the range [L, R] for some L, R (given in each query).
Constrains: N <= 100,000, K <= 100,000, |a[i]| <= 10^9.
I have tried but still unsuccessfully. Could someone please help me? Thank you very much!
Can you answer this queries 1. You can solve it using segment tree.
That is the same problem, isn't it? Well, I have some ideas now, just wonder why I had no ideas when looking at it before.
Can you check my idea before I implement it:
Node x controls range [l[x], r[x]], mid = (l+r) / 2. First case, [i,j] belongs to [l[x*2],r[x*2]]. Second case, [i,j] belongs to [l[x*2+1],r[x*2+1]]. Third case, i belongs to [l[x*2],r[x*2]], j belongs to [l[x*2+1],r[x*2+1]], use binary search to find i, j.
However, my idea is O(nlog^2n). Could you please tell me if there is any O(nlogn) solution? Thank you very much.
Yes.
C++ code
Idea
Segment Tree, in each node you should maintain: max-prefix-sum, max-suffix-sum, ans sum of all elements of the range, with that information you can merge two nodes to construct a parent node.
Sorry for my too poor english. :-(