Maximum sum such that no two elements are adjacent | Set 2 | Python 3 program to implement above approach ; variable to store states of dp ; variable to check if a given state has been solved ; Function to find the maximum sum subsequence such that no two elements are adjacent ; Base case ; To check if a state has been solved ; Required recurrence relation ; Returning the value ; Driver code
maxLen = 10 NEW_LINE dp = [ 0 for i in range ( maxLen ) ] NEW_LINE v = [ 0 for i in range ( maxLen ) ] NEW_LINE def maxSum ( arr , i , n ) : NEW_LINE INDENT if ( i >= n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( v [ i ] ) : NEW_LINE INDENT return dp [ i ] NEW_LINE DEDENT v [ i ] = 1 NEW_LINE dp [ i ] = max ( maxSum ( arr , i + 1 , n ) , arr [ i ] + maxSum ( arr , i + 2 , n ) ) NEW_LINE return dp [ i ] NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 12 , 9 , 7 , 33 ] NEW_LINE n = len ( arr ) NEW_LINE print ( maxSum ( arr , 0 , n ) ) NEW_LINE DEDENT