CandidFlakes's blog

By CandidFlakes, history, 2 weeks ago, In English

This is the question I am trying to solve. This is my attempt.

To find minimum is easy. For maximum I am iterating from end and finding lower bound, then upto the lower bound index I can assign maximum value to the number.

This approach is giving WA on Test 2. Please help me correct my approach?

I will be thankful for any help!

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
to find max d for index i you have to calculate longest segment i..j
such that for each k i <= k < j
B[k] >= A[k + 1]
D[i]max = B[j] - A[i]

brute way to calculate such segment is O(n^2) start from i and move forward
until the above condition is satisfied 

better way is start from back and keep extending segment backwards until the condition holds
if the condition is violated end the segment and start a new segment and do the same.
code