finding maximum of a subarray

Question

Preprocess an array A in O(n log n) time so that you can answer queries of the form findmax(i,j): find the maximum value in an interval [i; j] (that is, the maximum value among the array elements A[i],A[i + 1],...,A[j]) in O(1)) time per query.

Additional question: Show how to preprocess in O(n) time so that you can answer the above queries in O(log n) time.

What have you tried so far? Right now it looks like you've copied and pasted this question verbatim from a problem set or coding challenge website, which gives us very little reason to want to help you at all. — templatetypedef
– templatetypedef, Commented Feb 24, 2013 at 19:31
I have tried DP and this is past year informatics olympiad question. :) — 1234
– 1234, Commented Feb 24, 2013 at 19:44

IVlad · Accepted Answer · 2013-02-24 19:39:52Z

2

The problem is known as range minimum (maximum) query - RMQ. The link basically answers both of your questions.

The classic solutions are dynamic programming and segment trees.

answered Feb 24, 2013 at 19:39

IVlad

43.6k13 gold badges115 silver badges184 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

finding maximum of a subarray

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related