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!