Maximum sub | Function to return the maximum sum of the sub - sequence such that two consecutive elements have a difference of at least 3 in their indices in the given array ; If there is a single element in the array ; Either select it or don 't ; If there are two elements ; Either select the first element or don 't ; Either select the first or the second element or don 't select any element ; Either select the first element or don 't ; Either select the first or the second element or don 't select any element ; Either select first , second , third or nothing ; For the rest of the elements ; Either select the best sum till previous_index or select the current element + best_sum till index - 3 ; Driver code
def max_sum ( a , n ) : NEW_LINE INDENT dp = [ 0 ] * n ; NEW_LINE if ( n == 1 ) : NEW_LINE INDENT dp [ 0 ] = max ( 0 , a [ 0 ] ) ; NEW_LINE DEDENT elif ( n == 2 ) : NEW_LINE INDENT dp [ 0 ] = max ( 0 , a [ 0 ] ) ; NEW_LINE dp [ 1 ] = max ( a [ 1 ] , dp [ 0 ] ) ; NEW_LINE DEDENT elif ( n >= 3 ) : NEW_LINE INDENT dp [ 0 ] = max ( 0 , a [ 0 ] ) ; NEW_LINE dp [ 1 ] = max ( a [ 1 ] , max ( 0 , a [ 0 ] ) ) ; NEW_LINE dp [ 2 ] = max ( a [ 2 ] , max ( a [ 1 ] , max ( 0 , a [ 0 ] ) ) ) ; NEW_LINE i = 3 ; NEW_LINE while ( i < n ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i - 1 ] , a [ i ] + dp [ i - 3 ] ) ; NEW_LINE i += 1 ; NEW_LINE DEDENT DEDENT return dp [ n - 1 ] ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , - 2 , 4 , 3 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE print ( max_sum ( arr , n ) ) ; NEW_LINE DEDENT