Maximize the numbers of splits in an Array having sum divisible by 3 | Python3 program for 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
def calculate_maximum_splits ( arr , N ) : NEW_LINE INDENT pre = [ 0 , - 1 , - 1 ] NEW_LINE dp = [ 0 for i in range ( N ) ] NEW_LINE C = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT C = C + arr [ i ] NEW_LINE C = C % 3 NEW_LINE if pre [ C ] == - 1 : NEW_LINE INDENT dp [ i ] = dp [ i - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = max ( dp [ i - 1 ] , dp [ pre [ C ] ] + 1 ) NEW_LINE DEDENT pre [ C ] = i NEW_LINE DEDENT return dp [ N - 1 ] NEW_LINE DEDENT arr = [ 2 , 36 , 1 , 9 , 2 , 0 , 1 , 8 , 1 ] NEW_LINE N = len ( arr ) NEW_LINE print ( calculate_maximum_splits ( arr , N ) ) NEW_LINE