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
function max_sum ( a , n ) { let dp = new Array ( 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 ] ) ) ) ; let i = 3 ; while ( i < n ) { dp [ i ] = Math . max ( dp [ i - 1 ] , a [ i ] + dp [ i - 3 ] ) ; i ++ ; } } return dp [ n - 1 ] ; } let arr = [ 1 , 2 , - 2 , 4 , 3 ] ; let n = arr . length ; document . write ( max_sum ( arr , n ) ) ;