Wednesday, November 30, 2011

A Java program to find the length of the longest non decreasing subsequence from a group of integers (Java)

//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

No comments:

Post a Comment