Longest Increasing Subsequence problem
Given an array of numbers, we have to find the longest sub sequence of that array which is strictly increasing.For example in the following array [8 1 4 2 7 9 5] {8,9}{1,4,7,9}{1,2,7,9}{1,2,5}{1,2,7}{1,2,9} are some of the increasing sub-sequences. The second and third are the longest increasing sub sequences with length 4. Our job is…