//This Java program first accepts a number from the user

//and then accepts that many integers. The program then, using

//dynamic programming, finds the length of the longest

//subsequence of integers such that they are not in

//decreasing order.

//SEQUENCE : A subsequence is a sequence that can

//be derived from another sequence by deleting some

//elements without changing the order of the remaining

//elements. For example, the sequence <1,4,6> is a

//subsequence of <2,1,5,6,4,7,6>.

//Sample Output :-

/*Enter number of integers : 8

Enter the integers :-

-2

5

3

4

10

7

9

12

Longest non-decreasing sequence is of length : 6

*/

import java.util.*;

class longestNonDecreasingSequence

{

public static void main()

{

int n;

System.out.print("Enter number of integers : ");

Scanner sc=new Scanner(System.in);

n=sc.nextInt();

int a[]=new int[n];

int i;

System.out.println("Enter the integers :-\n");

for(i=0;i<n;i++)a[i]=sc.nextInt();

int s[]=new int[n];

for(i=0;i<n;i++)s[i]=1;

int j,k=0;

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

{

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

{

if(a[i]>=a[j])

{

k=s[j]+1;

if(s[i]<=k)

{

s[i]=k;

}

}

}

}

int ans=a[0];;

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

{

if(s[i]>=ans)

{

ans=s[i];

}

}

System.out.print("\nLongest non-decreasing sequence is of length : "+ans);

}

}

//Author : Mayank Rajoria

//and then accepts that many integers. The program then, using

//dynamic programming, finds the length of the longest

//subsequence of integers such that they are not in

//decreasing order.

//SEQUENCE : A subsequence is a sequence that can

//be derived from another sequence by deleting some

//elements without changing the order of the remaining

//elements. For example, the sequence <1,4,6> is a

//subsequence of <2,1,5,6,4,7,6>.

//Sample Output :-

/*Enter number of integers : 8

Enter the integers :-

-2

5

3

4

10

7

9

12

Longest non-decreasing sequence is of length : 6

*/

import java.util.*;

class longestNonDecreasingSequence

{

public static void main()

{

int n;

System.out.print("Enter number of integers : ");

Scanner sc=new Scanner(System.in);

n=sc.nextInt();

int a[]=new int[n];

int i;

System.out.println("Enter the integers :-\n");

for(i=0;i<n;i++)a[i]=sc.nextInt();

int s[]=new int[n];

for(i=0;i<n;i++)s[i]=1;

int j,k=0;

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

{

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

{

if(a[i]>=a[j])

{

k=s[j]+1;

if(s[i]<=k)

{

s[i]=k;

}

}

}

}

int ans=a[0];;

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

{

if(s[i]>=ans)

{

ans=s[i];

}

}

System.out.print("\nLongest non-decreasing sequence is of length : "+ans);

}

}

//Author : Mayank Rajoria

## No comments:

## Post a Comment