Maximize the numbers of splits in an Array having sum divisible by 3 | C ++ program for the above approach ; Prefix array storing right most index with prefix sums 0 , 1 , 2 ; dp array ; Current prefix sum ; Calculating the prefix sum modulo 3 ; We dont have a left pointer with prefix sum C ; We cannot consider i as a right pointer of any segment ; We have a left pointer pre [ C ] with prefix sum C ; i is the rightmost index of prefix sum C ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int calculate_maximum_splits ( int arr [ ] , int N ) { int pre [ ] = { 0 , -1 , -1 } ; int dp [ N ] ; memset ( dp , 0 , sizeof ( dp ) ) ; int C = 0 ; for ( int i = 0 ; i < N ; i ++ ) { C = C + arr [ i ] ; C = C % 3 ; if ( pre [ C ] == -1 ) { dp [ i ] = dp [ i - 1 ] ; } else { dp [ i ] = max ( dp [ i - 1 ] , dp [ pre [ C ] ] + 1 ) ; } pre [ C ] = i ; } return dp [ N - 1 ] ; } int main ( ) { int arr [ ] = { 2 , 36 , 1 , 9 , 2 , 0 , 1 , 8 , 1 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << ( calculate_maximum_splits ( arr , N ) ) ; }