1

We have an array of integer numbers. We want to know for each element whether that element is contained at least in one LIS of many LISs of our array or not. We want to know this for all elements in the array in less than O(n2).

For example array [2, 4, 3, 2, 5] has two LISs. All elements in the array belong to at least one of these LISs, exept the 4th element which does not belong to any LIS.

I know an easy solution which uses dfs, but its runtime is O(n2).

Chloe
  • 75
  • 6
  • 1
    Possible duplicate of [How to determine the longest increasing subsequence using dynamic programming?](https://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming) – Aurel Bílý Jul 12 '17 at 21:36
  • @AurelBílý: That only finds *a* longest increasing subsequence. There can be many. It doesn't let us determine whether or not arbitrary input elements have a LIS they're a member of. – user2357112 Jul 12 '17 at 21:41
  • Ah, I misunderstood your question, sorry. – Aurel Bílý Jul 12 '17 at 21:42
  • @AurelBílý You're welcome! – Chloe Jul 12 '17 at 21:46
  • In which case, https://stackoverflow.com/questions/9554266/finding-all-possible-longest-increasing-subsequence to find all LISs and mark elements which are part of LISs, then find the ones that haven't been marked? – Aurel Bílý Jul 12 '17 at 21:47
  • @user2357112 Determine the LIS, add all elements within the LIS to a set and youre done. Since the most common algorithms already involve sets it becomes fairly trivial to alter the answer from the question marked as dupe to solve this problem. –  Jul 12 '17 at 21:49
  • @AurelBílý What is the time complexity? – Chloe Jul 12 '17 at 21:50
  • 1
    @Paul: "**the**" LIS is where you're making your mistake. It's not just one. – user2357112 Jul 12 '17 at 21:50
  • Why not make a hash set of longest running sequence and do a constant lookup – Pushan Gupta Jul 12 '17 at 21:51
  • @Chloe The second answer quotes "O(n + Kl(p)) and space complexity of O(n), where n is the length of a permutation p, l(p) is the length of its longest increasing subsequence and K is the number of such subsequences." Then finding the unmarked elements is just a linear search. – Aurel Bílý Jul 12 '17 at 21:52
  • @VidorVistrom Longest running sequence in each step may not create an LIS of whole array. – Chloe Jul 12 '17 at 21:53
  • @AurelBílý: There could be exponentially many LISs, so you'll need to make some adjustments to not redo the work for overlapping sections of different LISs. I think, but I have not proven, that it is possible to make such adjustments. – user2357112 Jul 12 '17 at 21:54
  • I remember there was a nlogn solution for LIS. Convert each list to HashSet. And then do a lookup in each hashset. I mean you could create a list of hashsets and iterate over it. – Pushan Gupta Jul 12 '17 at 22:02
  • @VidorVistrom I did'nt understand your solution very well. Can you explain more. I know there is an O(n.logn) solution for LIS which uses segment tree but don't know that solution in detail. – Chloe Jul 12 '17 at 22:08
  • https://stackoverflow.com/questions/22923646/number-of-all-longest-increasing-subsequences After some tweaks, every element instead of being entered to a list can be added directly to a hashmap. Make a list of hashmaps. So each item in the list will be LIS in the form of hashmap. Now all you have to do is iterate through just these list for each element. Last part is inevitable anyhow – Pushan Gupta Jul 12 '17 at 22:18
  • Algorithm outline: A traditional LIS algorithm can be adapted to compute the length of "the" longest increasing subsequence ending at each element of the input. By running it "in reverse", we can compute the length of "the" longest increasing subsequence *beginning* at each element of the input. We can put these lengths together to determine whether each input element is a member of some LIS of the entire input. – user2357112 Jul 12 '17 at 22:23
  • @user2357112 Thank you so much! Very clever solution. Can the LIS ending at each element and beginning from each element be computed in O(n.logn) instead of traditional O(n^2) dp solution? – Chloe Jul 12 '17 at 22:37
  • @Chloe: By "traditional" LIS algorithm, I'm referring to O(nlogn) dynamic programming solutions. For example, the one on [Wikipedia](https://en.wikipedia.org/wiki/Longest_increasing_subsequence), or the O(nlogn) one in [Aurel's first link](https://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming). – user2357112 Jul 12 '17 at 22:42

1 Answers1

0

Run an algorithm such as https://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms which computes, at each point, the length of the longest increasing subsequence ending at that point.

Run the same algorithm using the data in reversed order, to compute, for each point, the length of the longest increasing subsequence starting at that point.

For each point add the two computed lengths. The point is on a longest increasing subsequence if this sum is equal to the largest sum found.

The alogorithm quoted takes time O(n log n) for each pass and the sum is only O(log n) so the total is O(n log n)

mcdowella
  • 19,301
  • 2
  • 19
  • 25