Partition an array such into maximum increasing segments | C ++ program to divide into maximum number of segments ; Returns the maximum number of sorted subarrays in a valid partition ; Find minimum value from right for every index ; Finding the shortest prefix such that all the elements in the prefix are less than or equal to the elements in the rest of the array . ; if current max is less than the right prefix min , we increase number of partitions . ; Driver code ; Find minimum value from right for every index
#include <iostream> NEW_LINE using namespace std ; int sorted_partitions ( int arr [ ] , int n ) { int right_min [ n + 1 ] ; right_min [ n ] = INT8_MAX ; for ( int i = n - 1 ; i >= 0 ; i -- ) { right_min [ i ] = min ( right_min [ i + 1 ] , arr [ i ] ) ; } int partitions = 0 ; for ( int current_max = arr [ 0 ] , i = 0 ; i < n ; i ++ ) { current_max = max ( current_max , arr [ i ] ) ; if ( current_max <= right_min [ i + 1 ] ) partitions ++ ; } return partitions ; } int main ( ) { int arr [ ] = { 3 , 1 , 2 , 4 , 100 , 7 , 9 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int ans = sorted_partitions ( arr , n ) ; cout << ans << endl ; return 0 ; }