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

---

Program Code