Find the longest sorted sub-sequence in java

PROBLEM DESCRIPTION : Longest Sorted Sub-Sequence

Given a sequence of N integers / numbers A(1) … A(n), determine a contiguous sub-sequence (range [i,j]) of maximum length in which the values in the sub-sequence form a strictly sorted sequence (ascending or descending order).

Example : 2 10 20 30 35 30 25 20 15 10 5 20 30 40 35 30 40 50
The longest sorted sub-sequence is 35 30 25 20 15 10 5 (length: 7)

SOURCE CODE : LongestSortedSubSequence.java

Longest Sorted Sub-Sequence is implemented in java as shown below :

/*
 * Copyright (c) 2011 Nanda Kishor
 * License : http://www.code-java.com/uses-gnu-gpl-v2-license
 * File: LongestSortedSubSequence.java
 * Tutorial : Find the longest sorted sub-sequence.
 */

import java.util.*;

public class LongestSortedSubSequence {

	public static void main(String[] args) {

		// Get the array size 'N' at run-time.
		System.out.print("How many elements you want to add : ");
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		// Create an array of size 'N' at runtime.
		int[] values = new int[n];

		// Adding 'N' elements to an array at runtime.
		for (int i=1; i<=n; i++) {
			System.out.print("Enter item#" + i + " : ");
			values[i-1] = scan.nextInt();
		}

		System.out.println("\nGiven list of elements are as follows :");
		for (int j=0; j < values.length; j++) {
			System.out.print(" " + values[j]);
		}

		int ascCount=0, desCount=0;
		int prevCountAsc = 0, prevCountDesc=0, prevDescIndex=0, prevAscIndex=0;

		for (int i=0; i < (values.length-1); i++) {
			if (values[i] < values[i+1]) {
				ascCount++;
			} else {
				if (++ascCount > prevCountAsc) {
					prevCountAsc = ascCount;
					prevAscIndex = (i+1) - prevCountAsc;
				}
				ascCount = 0;
			}

			if  (values[i] > values[i+1]) {
				desCount++;
			} else {
				if (++desCount > prevCountDesc) {
					prevCountDesc = desCount;
					prevDescIndex = (i+1) - prevCountDesc;
				}
				desCount = 0;
			}
		}

		System.out.println("\n\nLongest Ascending Sub Sequence, Length = " + prevCountAsc + " and starting index is " + (prevAscIndex+1));

		System.out.println("Longest Descending Sub Sequence, Length = " + prevCountDesc + " and starting index is " + (prevDescIndex+1));

		System.out.println("\nLongest Sorted Sub Sequence is as follows :");
		int startIdx, endIdx;
		if (prevCountAsc > prevCountDesc) {
			startIdx = prevAscIndex;
			endIdx = prevAscIndex + prevCountAsc;
		} else {
			startIdx = prevDescIndex;
			endIdx = prevDescIndex + prevCountDesc;
		}

		for (int idx=startIdx; idx < endIdx; idx++) {
			System.out.print(" " + values[idx]);
		}

	}
}

HOW IT WORKS ? [ Understanding the program ]

Logic (Line 33-56) : w.r.t Ascending sequence, keep increasing the count of ascending sequence (ascCount). When ascending sequence breaks, reset the ascCount to 0 and also reset the previous ascending count (prevCountAsc) & its starting index (prevAscIndex) only if ascCount is greater than prevCountAsc before reseting the ascCount.

Similarly apply the same logic for descending sequence too inside the same for loop.

Output (Line 62-74) : Prints the longest sorted subsequence starting from start index (startIdx, position where the sorted sub-sequence starts) until end index is reached (endIdx, position where the sorted sub-sequence ends).

HOW TO COMPILE the program ?

Use the following command to compile :

javac LongestSortedSubSequence.java

HOW TO RUN or execute the program ?

Use the following command to execute :

java LongestSortedSubSequence

OUTPUT :

LongestSortedSubSequence.java

LongestSortedSubSequence.java

TRY it yourself >> EXECUTE program online now :

Click to Compile and Run the LongestSortedSubSequence.java Program now.