CODEWITHSUNDEEP
algorithmdynamic-programming
1234
1234

Reputation: 23

finding maximum of a subarray

Preprocess an array A in O(n log n) time so that you can answer queries of the form fin dmax(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.

Upvotes: 0

Views: 462

Answers (1)

IVlad
IVlad

Reputation: 43477

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.

Upvotes: 2

Related Questions