Maximum number of partitions that can be sorted individually to make sorted | CPP program to find Maximum number of partitions such that we can get a sorted array . ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxPartitions ( int arr [ ] , int n ) { int ans = 0 , max_so_far = 0 ; for ( int i = 0 ; i < n ; ++ i ) { max_so_far = max ( max_so_far , arr [ i ] ) ; if ( max_so_far == i ) ans ++ ; } return ans ; } int main ( ) { int arr [ ] = { 1 , 0 , 2 , 3 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maxPartitions ( arr , n ) ; return 0 ; }