Longest Increasing Subsequence (LIS)

Example: arr[] = {10, 2, 1, 3, 5, 4, 6, 9, 8}

find out the LIS of this array

---

Steps:

• Make a table like this

  10	2	1	3	5	4	6	9	8
  1	1	1	1	1	1	1	1	1

• Start iterating from index 1 and check all of its previous indices with these condition

  • If arr[current index] is greater then arr[any of its previous index]

    • if table[this particular previous index] + 1 is greater then table[current index] then update table[current index]

    for(int i=1; i<len; i++)
    {
        // check current's previous
        for(int j=0; j<i; j++)
        {
            // if current is smaller or equal to any of previous
            if(arr[j] >= arr[i])
                continue;
            // is current item's LIS is not less then previous value
            if(ans[j]+1 <= ans[i])
                continue;
            // set the current item's LIS value
            ans[i] = ans[j]+1;
        }
    }

---

How the table is building

Array	10	2	1	3	5	4	6	9	8
initial	1	1	1	1	1	1	1	1	1
compare with 10	-	1	1	1	1	1	1	1	1
compare with 2	-	-	2	2	2	2	2	2	2
compare with 1	-	-	-	2	2	2	2	2	2
compare with 3	-	-	-	-	3	3	3	3	3
compare with 5	-	-	-	-	-	3	4	4	4
compare with 4	-	-	-	-	-	-	4	4	4
compare with 6	-	-	-	-	-	-	-	5	5
compare with 9	-	-	-	-	-	-	-	-	5
Final look	1	1	1	2	3	3	4	5	5

Here - indicate no compare

---

Program Code