1

Last week in an interview I was asked the above question and as expected I wasn't able to answer it correctly, later on when I checked I saw that its a dynamic programming based algorithm. I am not proficient in dynamic programming but suppose I was to design this algorithm then how should I approach it?

Suppose, I take idea from other divide and conquer algorithms like MergeSort and design the solution something like:

  1. Divide the sequence in two equal halves.
  2. Find the longest increasing sub-sequence in two halves
  3. Join the two halves.

Obviously there are missing pieces, but how get forward from here?

CodeYogi
  • 1,352
  • 1
  • 18
  • 41
  • i don't get it, you want just to apply random idea on any given problem and make it work? This problem can be solved in various ways, but only few are natural, dynamic programming is one of them, though obviously not the best (efficient) – Yerken Aug 03 '16 at 07:45
  • @Yerken As far as I know there is a improvement to the DP version using B-search, which achieve O(nlgn), is there any more efficient algorithm on LIS problem? – shole Aug 03 '16 at 08:01
  • @Yerken its not a random idea divide and conquer is a well known technique, second my basic aim was to know hoe to approach a problem when its totally new to you. – CodeYogi Aug 03 '16 at 10:01
  • @shole that's as efficient as you can get with this problem I believe. At least no faster approach is known to me. – Yerken Aug 03 '16 at 11:41
  • 1
    @shole Assuming you are working with integers, if you use a van Emde Boas tree instead of binary search, it can be done in O(n * lg(lg(n))) time, and with additional key renaming (as described [here](https://www.sciencedirect.com/science/article/pii/S0890540110000647)), it can be reduced to O(n * lg(lg(k))) time, where k is the length of the LIS. As far as I know, this is the fastest known algorithm. – Evan Bailey Oct 07 '21 at 02:31

1 Answers1

0

Your proposal won't work, because the longest sequences in both halves usually won't be contiguous, and there could exist a longer sequence when you join the halves.

You can fix this as follows:

  • in both halves, find the longest increasing sub-sequence, let L and R;

  • in both halves, find the longest increasing sub-sequence which is left-aligned, let LL and RL;

  • in both halves, find the longest increasing sub-sequence which is right-aligned, let LR and RR;

  • for the longest, keep the longest of L, R, LR+RL if the latter forms an increasing sequence;

  • for the left-aligned, keep LL or the whole left sub-sequence + RL if this forms an increasing sub-sequence;

  • for the right-aligned, keep RR or LR + the whole right sub-sequence if this forms an increasing sub-sequence.

All these operations are done in a single recursive process. When you concatenete two sub-sequences, checking if they form an increasing sub-sequence just takes the comparison of the facing elements.

Update:

This "fix" was not thoroughly checked.