Reduce array to longest sorted array possible by removing either half of given array in each operation | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ; } int partitionsArr ( int arr [ ] , int i , int j ) { if ( i >= j ) return 1 ; bool flag = isSortedparitions ( arr , i , j ) ; if ( flag ) { return ( j - i + 1 ) ; } int mid = ( i + j ) / 2 ; int X = partitionsArr ( arr , i , mid ) ; int Y = partitionsArr ( arr , mid + 1 , j ) ; return max ( X , Y ) ; } int main ( ) { int arr [ ] = { 11 , 12 , 1 , 2 , 13 , 14 , 3 , 4 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << partitionsArr ( arr , 0 , N - 1 ) ; return 0 ; }