Longest Increasing Subsequence

Input:
arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}

 1. list  = {0} - Initialize list to the empty set
 2. list  = {0,8} - New largest LIS
 3. list  = {0, 4} - Changed 8 to 4
 4. list  = {0, 4, 12} - New largest LIS
 5. list  = {0, 2, 12} - Changed 4 to 2
 6. list  = {0, 2, 10} - Changed 12 to 10
 7. list  = {0, 2, 6} - Changed 10 to 6
 8. list  = {0, 2, 6, 14} - New largest LIS
 9. list  = {0, 1, 6, 14} - Changed 2 to
 10. list = {0, 1, 6, 9} - Changed 14 to 9
 11. list = {0, 1, 5, 9} - Changed 6 to 5
 12. list = {0, 1, 6, 9, 13} - Changed 3 to 2
 13. list = {0, 1, 3, 9, 11} - New largest LIS
 14. list = {0, 1, 3, 9, 11} - Changed 9 to 5
 15. list = {0, 1, 3, 7, 11} - New largest LIS
 16. list = {0, 1, 3, 7, 11, 15} - New largest LIS

 So the length of the LIS is 6 (the size of list).

Output:
Longest Increasing Subsequence is:  [0, 1, 3, 7, 11, 15]