Partition an array such into maximum increasing segments | Java 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
import java . util . Arrays ; class GFG { static int sorted_partitions ( int arr [ ] ) { int n = arr . length ; int [ ] right_min = new int [ n + 1 ] ; right_min [ n ] = Integer . MAX_VALUE ; for ( int i = n - 1 ; i >= 0 ; i -- ) { right_min [ i ] = Math . min ( right_min [ i + 1 ] , arr [ i ] ) ; } int partitions = 0 ; for ( int current_max = arr [ 0 ] , i = 0 ; i < n ; i ++ ) { current_max = Math . max ( current_max , arr [ i ] ) ; if ( current_max <= right_min [ i + 1 ] ) partitions ++ ; } return partitions ; } public static void main ( String [ ] args ) { int [ ] arr = new int [ ] { 3 , 1 , 2 , 4 , 100 , 7 , 9 } ; int ans = sorted_partitions ( arr ) ; System . out . println ( ans ) ; } }