Maximum subsequence sum such that no three are consecutive | Returns maximum subsequence sum such that no three elements are consecutive ; Stores result for subarray arr [ 0. . i ] , i . e . , maximum possible sum in subarray arr [ 0. . i ] such that no three elements are consecutive . ; Base cases ( process first three elements ) ; Process rest of the elements We have three cases 1 ) Exclude arr [ i ] , i . e . , sum [ i ] = sum [ i - 1 ] 2 ) Exclude arr [ i - 1 ] , i . e . , sum [ i ] = sum [ i - 2 ] + arr [ i ] 3 ) Exclude arr [ i - 2 ] , i . e . , sum [ i - 3 ] + arr [ i ] + arr [ i - 1 ] ; Driver code
def maxSumWO3Consec ( arr , n ) : NEW_LINE INDENT sum = [ 0 for k in range ( n ) ] NEW_LINE if n >= 1 : NEW_LINE INDENT sum [ 0 ] = arr [ 0 ] NEW_LINE DEDENT if n >= 2 : NEW_LINE INDENT sum [ 1 ] = arr [ 0 ] + arr [ 1 ] NEW_LINE DEDENT if n > 2 : NEW_LINE INDENT sum [ 2 ] = max ( sum [ 1 ] , max ( arr [ 1 ] + arr [ 2 ] , arr [ 0 ] + arr [ 2 ] ) ) NEW_LINE DEDENT for i in range ( 3 , n ) : NEW_LINE INDENT sum [ i ] = max ( max ( sum [ i - 1 ] , sum [ i - 2 ] + arr [ i ] ) , arr [ i ] + arr [ i - 1 ] + sum [ i - 3 ] ) NEW_LINE DEDENT return sum [ n - 1 ] NEW_LINE DEDENT arr = [ 100 , 1000 , 100 , 1000 , 1 ] NEW_LINE n = len ( arr ) NEW_LINE print maxSumWO3Consec ( arr , n ) NEW_LINE