Maximize the numbers of splits in an Array having sum divisible by 3 | Javascript 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
function calculate_maximum_splits ( arr , N ) { var pre = [ 0 , - 1 , - 1 ] ; var i ; var dp = new Array ( N ) ; for ( i = 0 ; i < N ; i ++ ) dp [ i ] = 0 ; var C = 0 ; for ( i = 1 ; i < N ; i ++ ) { C = C + arr [ i ] ; C = C % 3 ; if ( pre [ C ] == - 1 ) { dp [ i ] = dp [ i - 1 ] ; } else { dp [ i ] = Math . max ( dp [ i - 1 ] , dp [ pre [ C ] ] + 1 ) ; } pre [ C ] = i ; } document . write ( dp [ N - 1 ] ) ; } var arr = [ 2 , 36 , 1 , 9 , 2 , 0 , 1 , 8 , 1 ] ; var N = arr . length ; calculate_maximum_splits ( arr , N ) ;