Maximize the numbers of splits in an Array having sum divisible by 3 | C # implementation of 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
using System ; class GFG { static int calculate_maximum_splits ( int [ ] arr , int N ) { int [ ] pre = { 0 , - 1 , - 1 } ; int [ ] dp = new int [ N ] ; for ( int i = 0 ; i < N ; i ++ ) { dp [ i ] = 0 ; } int C = 0 ; for ( int i = 0 ; i < N ; i ++ ) { C = C + arr [ i ] ; C = C % 3 ; if ( pre [ C ] == - 1 ) { if ( 1 <= i ) dp [ i ] = dp [ i - 1 ] ; } else { dp [ i ] = Math . Max ( dp [ i - 1 ] , dp [ pre [ C ] ] + 1 ) ; } pre [ C ] = i ; } return dp [ N - 1 ] ; } public static void Main ( string [ ] args ) { int [ ] arr = { 2 , 36 , 1 , 9 , 2 , 0 , 1 , 8 , 1 } ; int N = arr . Length ; Console . Write ( calculate_maximum_splits ( arr , N ) ) ; } }