duckladydinh's blog

A variant of Max-Sum Subsequence?
By duckladydinh, history, 8 years ago, In English

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!

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Can you answer this queries 1. You can solve it using segment tree.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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. :-(

→ Reply