soft_and_silent's blog

By soft_and_silent, history, 2 months ago, In English,

I know there is kakdane's algorithm . And gain we can find this using divide and conquer method . But my question was can i find maximum subarray using segment tree? Thank in advance .

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

»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Yes.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Of course. Just do a prefix sum. Then build a RMQ segment tree over the prefix sum array.

For each element in your prefix sum array, query the minimum element to the left of it using your segment tree. Take the difference of the two. Call this Ai for element with index i.

Max subarray sum is the max A over all i.