shuprog1's blog

Calculate length of longest increasing subsequence of all subarrays of an array
By shuprog1, 9 years ago, In English

Given an array A of length N, what is the best approach to answer queries of the form (i,j) where i and j are the indices of the array. Answer to a query (i,j) is the length of longest increasing subsequence of subarray from i to j. I am thinking of making a 2-D matrix which stores the length of LIS of all subarrays and then answering queries in O(1). How should I go about making that 2-D matrix? Or is there a better approach?

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.hackerearth.com/encoder15/algorithm/boogeyman/

This is the same problem .. you can look at some submissions from the leader board

→ Reply