Longest Increasing Subsequence

-

Given a sequence A of size N, find the length of the longest increasing subsequence from a given sequence . The longest increasing subsequence means to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible.This subsequence is not necessarily contiguous, or unique.

Note: Duplicate numbers are not counted as increasing subsequence.

Input:
The first line contains an integer T, depicting total number of test cases. Then following T lines contains an integer N depicting the size of array and next line followed by the value of array.

Output:
For each testcase, in a new line, print the Max length of the subsequence in a separate line.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 1000
0 ≤ A[i] ≤ 300

Example:
Input:
2
16
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
6
5 8 3 7 9 1

Output:
6
3

Explanation:
Testcase 2: Longest increasing subsequence is of size 3 with elements (there are many subsequence, but listing one of them): 5 7 9.

The link of this problem is https://practice.geeksforgeeks.org/problems/longest-increasing-subsequence/0
 

Solution(CPP):

#include<iostream>

using namespace std;

int main()

{

    int t;

    cin>>t;

    while(t--)

    {

        int n;

        cin>>n;

        int a[n];

        for(int i=0;i<n;i++)

        {

            cin>>a[i];

        }

        int lis[n];

        for(int i=0;i<n;i++)

        {

            lis[i]=1;

        }

        for(int i=1;i<n;i++)

        {

            for(int j=0;j<i;j++)

            {

                if(a[i]>a[j] && lis[i]<lis[j]+1)

                {

                    lis[i]=lis[j]+1;

                }

            }

        }

        int max=lis[0];

        for(int i=1;i<n;i++)

        {

            if(max<lis[i])

            {

                max=lis[i];

            }

        }

        cout<<max<<endl;

    }

//code

return 0;

}



Comments

Post a Comment

Popular posts from this blog

Floyd Warshall algorithm and it's applications.

-
The floyd warshall algorithm is for solving the All Pairs Shortest Path problem. The problem is to find shortest distances between every pair of vertices in a given edge weighted directed Graph. INPUT : Input will be a distance matrix (let say dis) , where dis[i][j] will represent the distance between the ith and jth node in the graph. and you have to input 2 nodes (a and b) between whom you want to find the shortest distance . OUTPUT: Output will be the shortest distance between the two node a and b. and it will also output the path between the two node through which you can achieve the shortest distance. ...................................................................................................................................................................... #include<bits/stdc++.h> using namespace std; #define inf 1000 void iter(int dis[][5],int seq[][5],int k) {     for(int i=0;i<5;i++)     {         ...
Read more

Digits in Factorial

-
Problem Statement:   Given an integer   N . The task is to find the number of digits that appear in its factorial, where factorial is defined as, factorial(n) = 1*2*3*4……..*N and factorial(0) = 1. Example 1: Input: N = 5 Output: 3 Explanation: Factorial of 5 is 120. Number of digits in 120 is 3 (1, 2, and 0) Example 2: Input: N = 120 Output: 199 Explanation: The number of digits in 200! is 199 Your Task: You don't need to read input or print anything. Your task is to complete the function  digitsInFactorial()  that takes  N  as parameter and returns  number of digits  in factorial of  N . Expected Time Complexity  : O(N) Expected Auxilliary Space  : O(1) Constraints: 1 ≤ N ≤ 10 4  The link of this problem is  https://practice.geeksforgeeks.org/problems/digits-in-factorial/1 Solution: Python3 import math def digitsInFactorial(N):     sum1=0     for i in range(1,N+1):         sum1+=mat...
Read more

Design a tiny URL or URL Shortner

-
Design a system that takes big URLs like “ http://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/ ” and converts them into a short  6 character URL . It is given that URLs are stored in database and every URL has an associated integer   id .  So your program should take an integer id and generate a 6 character long URL.  A URL character can be one of the following A lower case alphabet [‘a’ to ‘z’], total 26 characters An upper case alphabet [‘A’ to ‘Z’], total 26 characters A digit [‘0′ to ‘9’], total 10 characters There are total 26 + 26 + 10 = 62 possible characters. So the task is to convert an integer (database id) to a base 62 number where digits of 62 base are "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789" Input: The first line of input contains an integer T denoting the number of test cases.  The second line consists of a long integer. Output: For each testcase, in a new line, print the  shortened  strin...
Read more