Maximum sum such that exactly half of the elements are selected and no two adjacent | Python3 program to find maximum sum possible such that exactly floor ( N / 2 ) elements are selected and no two selected elements are adjacent to each other ; Function return the maximum sum possible under given condition ; Intitialising the dp table ; Base case ; Condition to select the current element ; Condition to not select the current element if possible ; Driver code
import sys NEW_LINE def MaximumSum ( a , n ) : NEW_LINE INDENT dp = [ [ 0 for i in range ( n + 1 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ j ] = - sys . maxsize - 1 NEW_LINE DEDENT DEDENT for i in range ( n + 1 ) : NEW_LINE INDENT dp [ i ] [ 0 ] = 0 NEW_LINE DEDENT for i in range ( 1 , n + 1 , 1 ) : NEW_LINE INDENT for j in range ( 1 , i + 1 , 1 ) : NEW_LINE INDENT val = - sys . maxsize - 1 NEW_LINE if ( ( i - 2 >= 0 and dp [ i - 2 ] [ j - 1 ] != - sys . maxsize - 1 ) or i - 2 < 0 ) : NEW_LINE INDENT if ( i - 2 >= 0 ) : NEW_LINE INDENT val = a [ i - 1 ] + dp [ i - 2 ] [ j - 1 ] NEW_LINE DEDENT else : NEW_LINE INDENT val = a [ i - 1 ] NEW_LINE DEDENT DEDENT if ( i - 1 >= j ) : NEW_LINE INDENT val = max ( val , dp [ i - 1 ] [ j ] ) NEW_LINE DEDENT dp [ i ] [ j ] = val NEW_LINE DEDENT DEDENT return dp [ n ] [ n // 2 ] 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