Search code examples
algorithmlcslis

How to prove correctness of the following algo

Problem is to find LIS(Longest Increasing Subsequence) of any given array. Ex. a[]={10,9,7,8,9}; length=3; {7,8,9}

So one way of doing in nlogn is

  1. Sort the array
  2. Take LCS of the the two Resulting is LIS.

Now I understood how to do it. But how do I prove it is correct. How to apply MI here?

Solution

  • In your case there is no need for induction, you have to show three things:

    • resulting method captures increasing sequence - comes directly from the fact that it is a part of sorted array
    • resulting subsequence exists in the input array - comes directly from the definition of LCS (common subsequence)
    • there is no longer increasing subsequence - you can easily show that the longest sequence has to be present in both input sequence (by definition) and in sorted array, so it would be also analyzed by LCS, thus it cannot be longer then the one returned by LCS.