Maximum sum such that exactly half of the elements are selected and no two adjacent | Function return the maximum sum possible under given condition ; Base case ; When i is odd ; When i is even ; Maximum of if we pick last element or not ; Driver code
def MaximumSum ( a , n ) : NEW_LINE INDENT dp = [ [ 0 for x in range ( 2 ) ] for y in range ( n + 1 ) ] NEW_LINE dp [ 2 ] [ 1 ] = a [ 1 ] NEW_LINE dp [ 2 ] [ 0 ] = a [ 0 ] NEW_LINE for i in range ( 3 , n + 1 ) : NEW_LINE INDENT if ( i & 1 ) : NEW_LINE INDENT temp = max ( [ dp [ i - 3 ] [ 1 ] , dp [ i - 3 ] [ 0 ] , dp [ i - 2 ] [ 1 ] , dp [ i - 2 ] [ 0 ] ] ) NEW_LINE dp [ i ] [ 1 ] = a [ i - 1 ] + temp NEW_LINE dp [ i ] [ 0 ] = max ( [ a [ i - 2 ] + dp [ i - 2 ] [ 0 ] , a [ i - 2 ] + dp [ i - 3 ] [ 1 ] , a [ i - 2 ] + dp [ i - 3 ] [ 0 ] , a [ i - 3 ] + dp [ i - 3 ] [ 0 ] ] ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] [ 1 ] = ( a [ i - 1 ] + max ( [ dp [ i - 2 ] [ 1 ] , dp [ i - 2 ] [ 0 ] , dp [ i - 1 ] [ 0 ] ] ) ) NEW_LINE dp [ i ] [ 0 ] = a [ i - 2 ] + dp [ i - 2 ] [ 0 ] NEW_LINE DEDENT DEDENT return max ( dp [ n ] [ 1 ] , dp [ n ] [ 0 ] ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT A = [ 1 , 2 , 3 , 4 , 5 , 6 ] NEW_LINE N = len ( A ) NEW_LINE print ( MaximumSum ( A , N ) ) NEW_LINE DEDENT