Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

soft_and_silent's blog

By soft_and_silent, history, 7 weeks 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

»
7 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Yes.

»
7 weeks 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.