Maximum subsequence sum such that no three are consecutive | Python3 program to find the maximum sum such that no three are consecutive using recursion . ; Returns maximum subsequence sum such that no three elements are consecutive ; 3 Base cases ( process first three elements ) ; Process rest of the elements We have three cases ; Driver code
arr = [ 100 , 1000 , 100 , 1000 , 1 ] NEW_LINE sum = [ - 1 ] * 10000 NEW_LINE def maxSumWO3Consec ( n ) : NEW_LINE INDENT if ( sum [ n ] != - 1 ) : NEW_LINE INDENT return sum [ n ] NEW_LINE DEDENT if ( n == 0 ) : NEW_LINE INDENT sum [ n ] = 0 NEW_LINE return sum [ n ] NEW_LINE DEDENT if ( n == 1 ) : NEW_LINE INDENT sum [ n ] = arr [ 0 ] NEW_LINE return sum [ n ] NEW_LINE DEDENT if ( n == 2 ) : NEW_LINE INDENT sum [ n ] = arr [ 1 ] + arr [ 0 ] NEW_LINE return sum [ n ] NEW_LINE DEDENT sum [ n ] = max ( max ( maxSumWO3Consec ( n - 1 ) , maxSumWO3Consec ( n - 2 ) + arr [ n ] ) , arr [ n ] + arr [ n - 1 ] + maxSumWO3Consec ( n - 3 ) ) NEW_LINE return sum [ n ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = len ( arr ) NEW_LINE print ( maxSumWO3Consec ( n ) ) NEW_LINE DEDENT