tom's blog

Maximum sum subarray problem revisited
By tom, history, 7 years ago, In English

Hello everyone,

I would like to quickly compute maximum sum subarray with queries (change ith element to x). Can we do it faster than O(log(n)) per query?

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

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

UPD:I am sorry I misread the question

→ Reply
»
7 years ago, # |
  Vote: I like it +31 Vote: I do not like it

The answer is no, and here is the reasoning. You can answer this question using some logic by reducing the problem to a known one.

If your initial array is a1, a2, ... an — you can replace it with [a1, -a1, a2, -a2, ... ]. Notice that when you query a range, it is the same as querying maximum value of ai in the range. Updates remain the same.

If you suppose can do your problem in faster than log(n), then you can do this in faster than log(n), which is at this point in time, obviously impossible (otherwise segment trees would be sub-optimal).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    Using your transition to "maximum value in the range" problem, one can also pick a different reasoning: if you can solve it faster than log(n), you can sort array faster than n * log(n) — just pick maximum element and replace it with  - INF n times.

    → Reply