Maximum sub | C ++ implementation of the approach ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int max_sum ( int a [ ] , int n ) { int dp [ n ] ; if ( n == 1 ) { dp [ 0 ] = max ( 0 , a [ 0 ] ) ; } else if ( n == 2 ) { dp [ 0 ] = max ( 0 , a [ 0 ] ) ; dp [ 1 ] = max ( a [ 1 ] , dp [ 0 ] ) ; } else if ( 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 ] ) ) ) ; int i = 3 ; while ( i < n ) { dp [ i ] = max ( dp [ i - 1 ] , a [ i ] + dp [ i - 3 ] ) ; i ++ ; } } return dp [ n - 1 ] ; } int main ( ) { int arr [ ] = { 1 , 2 , -2 , 4 , 3 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << max_sum ( arr , n ) ; return 0 ; }