Maximum sum subsequence with at | Java program to find maximum sum subsequence such that elements are at least k distance away . ; MS [ i ] is going to store maximum sum subsequence in subarray from arr [ i ] to arr [ n - 1 ] ; We fill MS from right to left . ; Driver code
import java . io . * ; class GFG { static int maxSum ( int arr [ ] , int N , int k ) { int MS [ ] = new int [ N ] ; MS [ N - 1 ] = arr [ N - 1 ] ; for ( int i = N - 2 ; i >= 0 ; i -- ) { if ( i + k + 1 >= N ) MS [ i ] = Math . max ( arr [ i ] , MS [ i + 1 ] ) ; else MS [ i ] = Math . max ( arr [ i ] + MS [ i + k + 1 ] , MS [ i + 1 ] ) ; } return MS [ 0 ] ; } public static void main ( String [ ] args ) { int N = 10 , k = 2 ; int arr [ ] = { 50 , 70 , 40 , 50 , 90 , 70 , 60 , 40 , 70 , 50 } ; System . out . println ( maxSum ( arr , N , k ) ) ; } }