Reduce array to longest sorted array possible by removing either half of given array in each operation | 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
def isSortedparitions ( arr , i , j ) : NEW_LINE INDENT for k in range ( i + 1 , j + 1 ) : NEW_LINE INDENT if ( arr [ k ] < arr [ k - 1 ] ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT DEDENT return 1 NEW_LINE DEDENT def partitionsArr ( arr , i , j ) : NEW_LINE INDENT if ( i >= j ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT flag = int ( isSortedparitions ( arr , i , j ) ) NEW_LINE if ( flag != 0 ) : NEW_LINE INDENT return ( j - i + 1 ) NEW_LINE DEDENT mid = ( i + j ) // 2 NEW_LINE X = partitionsArr ( arr , i , mid ) ; NEW_LINE Y = partitionsArr ( arr , mid + 1 , j ) NEW_LINE return max ( X , Y ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 11 , 12 , 1 , 2 , 13 , 14 , 3 , 4 ] NEW_LINE N = len ( arr ) NEW_LINE print ( partitionsArr ( arr , 0 , N - 1 ) ) NEW_LINE DEDENT