Reduce array to longest sorted array possible by removing either half of given array in each operation | Java program to implement the above approach ; Function to check if the subarray arr [ i . . j ] is a sorted subarray or not ; Traverse all elements of the subarray arr [ i ... j ] ; If the previous element of the subarray exceeds current element ; Return 0 ; Return 1 ; Recursively partition the array into two equal halves ; If atmost one element is left in the subarray arr [ i . . j ] ; Checks if subarray arr [ i . . j ] is a sorted subarray or not ; If the subarray arr [ i ... j ] is a sorted subarray ; Stores middle element of the subarray arr [ i . . j ] ; Recursively partition the current subarray arr [ i . . j ] into equal halves ; Driver Code
import java . util . * ; class GFG { static int isSortedparitions ( int arr [ ] , int i , int j ) { for ( int k = i + 1 ; k <= j ; k ++ ) { if ( arr [ k ] < arr [ k - 1 ] ) { return 0 ; } } return 1 ; } static int partitionsArr ( int arr [ ] , int i , int j ) { if ( i >= j ) return 1 ; int flag = ( int ) isSortedparitions ( arr , i , j ) ; if ( flag != 0 ) { return ( j - i + 1 ) ; } int mid = ( i + j ) / 2 ; int X = partitionsArr ( arr , i , mid ) ; int Y = partitionsArr ( arr , mid + 1 , j ) ; return Math . max ( X , Y ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 11 , 12 , 1 , 2 , 13 , 14 , 3 , 4 } ; int N = arr . length ; System . out . print ( partitionsArr ( arr , 0 , N - 1 ) ) ; } }