human
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"
How can the above be solved in Python?
assistant
#Here is code to maximum sub and the other steps required.
 def max_sum ( a , n ) :
	dp = [ 0 ] * n ;
	if ( n == 1 ) :
		dp [ 0 ] = max ( 0 , a [ 0 ] ) ;
	elif ( n == 2 ) :
		dp [ 0 ] = max ( 0 , a [ 0 ] ) ;
		dp [ 1 ] = max ( a [ 1 ] , dp [ 0 ] ) ;
	elif ( n >= 3 ) :
		dp [ 0 ] = max ( 0 , a [ 0 ] ) ;
		dp [ 1 ] = max ( a [ 1 ] , max ( 0 , a [ 0 ] ) ) ;
		dp [ 2 ] = max ( a [ 2 ] , max ( a [ 1 ] , max ( 0 , a [ 0 ] ) ) ) ;
		i = 3 ;
		while ( i < n ) :
			dp [ i ] = max ( dp [ i - 1 ] , a [ i ] + dp [ i - 3 ] ) ;
			i += 1 ;
	return dp [ n - 1 ] ;
if __name__ == " _ _ main _ _ " :
	arr = [ 1 , 2 , - 2 , 4 , 3 ] ;
	n = len ( arr ) ;
	print ( max_sum ( arr , n ) ) ;