Maximum sum Subsequence with index difference K in Java
Given an array of integers named ar[] and an integer named k, the objective is to determine a subsequence within the array whose sum of its elements is maximum. Here, there is a constraint: the elements selected must have a minimum index difference of k. In other words, our task is to determine the maximum possible sum of a subsequence where the elements are has at least k indices difference in the original array.
Example 1:
Input: ar[] = [ 6, 10, 4, 3, 7, 9, 2, 5, 8 ]
K = 4
Output: 21
Explanation: We select the elements with a minimum index difference of 4, i.e., starting at index 0, then next choose index 4, after that index 8. The subsequence obtained is [6, 10, 7, 8]. Now adding all the elements in the subsequence, we get 21 which is the maximum sum.
Example 2:
Input: ar[] = [ 1, 4, 3, 5, 2, 7, 9]
K = 3
Output: 15
Explanation: We choose the elements with a minimum index difference of 3, beginning with index 0 and moving to index 3 and then to index 6. The subsequence created is [1, 5, 9]. Adding all of the elements in the subsequence gives 16, which is the maximum sum.
Approach: Using Dynamic Programming
Observe the steps to solve the problem with the help of dynamic programming.
Step 1: Create an ArrayList called dpAr and initialise it with 0’s to store the maximum sum subsequence.
Step 2: Iterate through the first kDiff elements of the input list named arL, and assign them as initial values for dpAr.
Step 3: Iterate through the remaining elements of list arL to determine the maximum sum of subsequence:
Step 3.1: For each element at index i, set dpAr[i] to the sum of the element at index i and the element kDiff indices before it, i.e., [dpAr[i - kDiff].
Step 4: Finally, return the maximum value in dpAr, which displays the maximum sum subsequence.
FileName: MaxSumOfSeqWithIndexKDiff.java
// importing util packages
import java.util.*;
public class MaxSumOfSeqWithIndexKDiff {
// method to find the maximum sum subsequence with index difference kDiff
public static int getMaxSumSubsequence(List arL,
int kDiff)
{
int nLen = arL.size();
// initializing an ArrayList to store the maximum sum subsequence
List dpAr = new ArrayList<>(Collections.nCopies(nLen, 0));
// assigning initial values of dpAr using first kDiff elements
for (int i = 0; i < kDiff; i++) {
dpAr.set(i, arL.get(i));
}
// calculating maximum sum subsequence for remaining elements
for (int i = kDiff; i < nLen; i++) {
dpAr.set(i, dpAr.get(i - kDiff) + arL.get(i));
}
return Collections.max(dpAr);
}
// main method
public static void main(String[] args)
{
// provide input Array values
List arL = Arrays.asList(6, 10, 4, 3, 7, 9, 2, 5, 8);
// provide k index difference value
int kDiff = 4;
System.out.println("The maximum possible sum of a sequence with index difference " +kDiff+ " is: ");
System.out.println(getMaxSumSubsequence(arL, kDiff));
}
}
Output:
The maximum possible sum of a sequence with index difference 4 is: 21
Complexity analysis: The first loop takes O(n) time iterates over the input array up to kDiff. The second loop takes O(n - kDiff) time to iterate over the remaining elements. Therefore, the overall time complexity is O(n), where n is the size of the input array. The space complexity also O(n) because the ArrayList named dpAr, stores the maximum sum subsequence. Also, the program uses constant space for integer variables. Therefore, the overall space complexity is o(n).