Partition an array such into maximum increasing segments | Python 3 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 sys NEW_LINE def sorted_partitions ( arr , n ) : NEW_LINE INDENT right_min = [ 0 ] * ( n + 1 ) NEW_LINE right_min [ n ] = sys . maxsize NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT right_min [ i ] = min ( right_min [ i + 1 ] , arr [ i ] ) NEW_LINE DEDENT partitions = 0 NEW_LINE current_max = arr [ 0 ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT current_max = max ( current_max , arr [ i ] ) NEW_LINE if ( current_max <= right_min [ i + 1 ] ) : NEW_LINE INDENT partitions += 1 NEW_LINE DEDENT DEDENT return partitions NEW_LINE DEDENT arr = [ 3 , 1 , 2 , 4 , 100 , 7 , 9 ] NEW_LINE n = len ( arr ) NEW_LINE ans = sorted_partitions ( arr , n ) NEW_LINE print ( ans ) NEW_LINE