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
using System ; class GFG { static int max_sum ( int [ ] a , int n ) { int [ ] dp = new int [ n ] ; if ( n == 1 ) { dp [ 0 ] = Math . Max ( 0 , a [ 0 ] ) ; } else if ( n == 2 ) { dp [ 0 ] = Math . Max ( 0 , a [ 0 ] ) ; dp [ 1 ] = Math . Max ( a [ 1 ] , dp [ 0 ] ) ; } else if ( n >= 3 ) { dp [ 0 ] = Math . Max ( 0 , a [ 0 ] ) ; dp [ 1 ] = Math . Max ( a [ 1 ] , Math . Max ( 0 , a [ 0 ] ) ) ; dp [ 2 ] = Math . Max ( a [ 2 ] , Math . Max ( a [ 1 ] , Math . Max ( 0 , a [ 0 ] ) ) ) ; int i = 3 ; while ( i < n ) { dp [ i ] = Math . Max ( dp [ i - 1 ] , a [ i ] + dp [ i - 3 ] ) ; i ++ ; } } return dp [ n - 1 ] ; } static public void Main ( ) { int [ ] arr = { 1 , 2 , - 2 , 4 , 3 } ; int n = arr . Length ; Console . Write ( max_sum ( arr , n ) ) ; } }