Java Program to Print the Longest Increasing Subarray

«
»

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

Problem Description

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

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

Output: 0 7 8 9

Problem Solution

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

Program/Source Code
advertisement
advertisement

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

1. In function longestIncreasingSubarray(), we declare array index [] to store the starting and ending index of the longest subarray.
2. The loop for(i=0; i<array.length-1; i++) is used to iterate through the array.
3. The condition if(array[i] < array[i+1]) is used to check if the current pair of elements is increasing.
4. If it is true, then a nested loop for(j = i+1; j<array.length-1; j++) is set-up to look for the end of the increasing subarray.
5. The condition if(max > index[1] – index[0] + 1) checks if the current subarray length, is greater than the previous one. It updates the index array, if it is true.
6. The variable max stores the length of the increasing subarray and variable start stores the starting index.

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

Runtime Test Cases
 
Case 1 (Simple Test Case - Mixed Elements):
 
Enter the size of the array
9
Enter array elements
5
6
3
0
7
8
9
1
2
The longest decreasing subarray is
0 7 8 9
 
Case 2 (Simple Test Case - Elements in Ascending Order):
 
Enter the size of the array
5
Enter array elements
1
2
3
4
5
The longest increasing subarray is
1 2 3 4 5 
 
Case 3 (Simple Test Case - Elements in Descending Order):
 
Enter the size of the array
6
Enter array elements
6
5
4
3
2
1
The longest increasing subarray is
6

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.