Java Program to Print the Longest Decreasing Subarray

«
»

This is the Java Program to Print the Longest Sub-Array that is decreasing.

Problem Description

Given an array of integers, find the longest contiguous subarray whose elements are decreasing, that is, the elements following the preceding elements in the subarray must be smaller than them.
Example:

Array = [5, 6, 3, 0, 7, 8, 9, 1, 2]

Output: 6 3 0

Problem Solution

Traverse the array from beginning to end and check for the first element which is greater than the element following it, from that index find out the subarray which is decreasing, if the current subarray length is greater than the previous subarray length, then update the longest decreasing subarray. Initially, the subarray would be of length one, referring to the first elements of the array.

Program/Source Code
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here is the source code of the Java Program to Print the Longest Sub-Array that is Decreasing. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. //Java Program to Print the Longest Sub-Array that is Decreasing
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6.  
  7. public class LongestDecreasingSubarray {
  8.     // Function to calculate the longest decreaing subarray
  9.     static int[] longestDecreasingSubarray(int[] array){
  10.         int[] index = new int[2];
  11.         int i,j,start = 0;
  12.         int max = 0;
  13.         for(i=0; i<array.length-1; i++){
  14.             max = 0;
  15.             if(array[i] > array[i+1]){
  16.                 start = i;
  17.                 max++;
  18.                 for(j = i+1; j<array.length-1; j++){
  19.                     if(array[j] < array[j+1])
  20.                         break;
  21.                     else
  22.                         max++;
  23.                 }
  24.                 if(max > index[1] - index[0] + 1){
  25.                     index[0] = start;
  26.                     index[1] = j--;
  27.                 }
  28.                 i = j--;
  29.             }
  30.         }
  31.         return index;
  32.     }
  33.     // Function to read input and display the user output
  34.     public static void main(String[] args) {
  35.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  36.         int size;
  37.         System.out.println("Enter the size of the array");
  38.         try {
  39.             size = Integer.parseInt(br.readLine());
  40.         } catch (Exception e) {
  41.             System.out.println("Invalid Input");
  42.             return;
  43.         }
  44.         int[] array = new int[size];
  45.         System.out.println("Enter array elements");
  46.         int i;
  47.         for (i = 0; i < array.length; i++) {
  48.             try {
  49.                 array[i] = Integer.parseInt(br.readLine());
  50.             } catch (Exception e) {
  51.                 System.out.println("An error occurred");
  52.             }
  53.         }
  54.         int[] index = longestDecreasingSubarray(array);
  55.         System.out.println("The longest decreasing subarray is");
  56.         for(i=index[0];i<=index[1];i++){
  57.             System.out.print(array[i] + " ");
  58.         }
  59.     }
  60. }
Program Explanation

1. In function longestDecreasingSubarray(), the array index is created to hold the starting and ending indexes of the longest decreasing subarray.
2. The loop for(i=0; i<array.length-1; i++) is used to traverse the array from left to right.
3. The condition if(array[i] > array[i+1]) checks if the current element is greater than the following element.
4. If the condition is true, then using the nested loop for(j = i+1; j<array.length-1; j++) the length of the decreasing subarray is calculated.
5. The condition if(max > index[1] – index[0] + 1) checks whether the current subarray is longer than the previous subarray.
6. If it is the indexes are updated.

Take Java Programming Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Time Complexity: O(n2) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Simple Test Case):
 
Enter the size of the array
9
Enter array elements
5
6
3
0
7
8
9
1
2
The longest decreasing subarray is
6 3 0
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
5
Enter array elements
9
7
5
3
1
The longest decreasing subarray is
9 7 5 3 1

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.