Longest Increasing Subsequence

Task: Given a sequence of an array of size N, find longest increasing sub-sequence from given sequence. The sub-sequence is need not to be continuous.

Example:

Input:

1

6

5 8 3 7 9 1

Output:

3 // 5 7 9

---

Here is the Code:

Program in C++:

1. #include<iostream>
2. using namespace std;
3. int longestIncreasingSubsequence(int *a,int n)
4. {
5.     int dp[n],lis=1;
6.     dp[0]=1;
7.     for(int i=1;i<n;i++)
8.     {
9.         int j=0,t=1;
10.         while(j<i)
11.         {
12.             if(a[i]>a[j]&&t<=dp[j])
13.             {
14.                 t++;
15.             }
16.             j++;
17.         }
18.         dp[i]=t;
19.         if(lis<dp[i]) lis=dp[i];
20.     }
21.     return lis;
22. }
23. int main()
24.  {
25. int t;
26. cin>>t;
27. while(t--)
28. {
29.     int n;
30.     cin>>n;
31.     int a[n];
32.     for(int i=0;i<n;i++)
33.     {
34.         cin>>a[i];
35.     }
36.     cout<<longestIncreasingSubsequence(a,n)<<endl;
37. }
38. return 0;
39. }

---

Here is the Video: