Maximum number of partitions that can be sorted individually to make sorted | Function to find maximum partitions . ; Find maximum in prefix arr [ 0. . i ] ; If maximum so far is equal to index , we can make a new partition ending at index i . ; Driver code
def maxPartitions ( arr , n ) : NEW_LINE INDENT ans = 0 ; max_so_far = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT max_so_far = max ( max_so_far , arr [ i ] ) NEW_LINE if ( max_so_far == i ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT arr = [ 1 , 0 , 2 , 3 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE print ( maxPartitions ( arr , n ) ) NEW_LINE