Maximum Sum Subsequence of Length K in Java
In this tutorial, we are going to learn about maximum sum subsequence of length K in Java. The aim is to calculate the largest feasible sum of rising subsequence S of length K such that S1=S2=S3……=Sk given an array sequence [X1, X2,... Xn].
Examples:
Example 1:
Input: n = 10, k = 4
A = [6, 9, 4, 8, 10, 7, 12, 13, 11, 5]
Output: 47
Explanation: The following is one potential length four rising subsequence with the highest possible sum: 6, 9, 10, 12. This subsequence has a sum of 6 + 9 + 10 + 12 = 47.
Example 2:
Input: n = 6, k = 2
A = [3, 7, 2, 8, 6, 9]
Output: 4
Explanation: 7, 9, is the highest sum that may be obtained from one potential length two ascending subsequence. 7 + 9 = 16 is the total of this subsequence.
Naïve approach:
ALGORITHM:
Step 1: Build a two-dimensional array dp, where each element (dp[i][j]) is the greatest sum subsequence of length j that ends at index i.
Step 2: Initialize all of the values in this array to -1.
Step 3: Loop over every entry in the input array arr. Since arr[i] is the greatest sum subsequence of length 1 ending at index i, dp[i][1] is set to arr[i] for each element arr[i]. Subsequently, the array is traversed once more, with each pair of elements (arr[j] and arr[i]) where j < i compared.
Step 4: Update dp[i][l + 1] for each conceivable length l from 1 to k-1 if arr[j] is less than arr[i], suggesting that arr[i] can extend an expanding subsequence after arr[j].
Step 5: Store the largest value in the variable ans after iterating over all values of dp[i][k] for various values of i.
Step 6: Represent the greatest sum of ascending subsequences of length k over the whole array is by the value.
Step 7: Return 0 if no increasing subsequence of length k is identified.
Filename: MaximumSubsequence.java
import java.util.*; public class MaximumSubsequence { static int calculateMaxSumOfIncreasingSubsequence(int[] elements, int length , int k) { // The maximum sum subsequence of length k is represented in the implementation as dp[length][k], and it ends at index length. int[][] dp = new int[length][k + 1]; int maxSum = -1; // Setting the value of -1 to initialize the entire multidimensional dp array for(int a = 0; a < length; a++) for(int b = 0; b < k + 1; b++) dp[a][b]=-1; // Initializing dp[i][1] with that array value means that for every ith location, a growing subsequence of length 1 equals that array's ith value. for (int a = 0; a < length; a++) { dp[a][1] = elements[a]; } // As we have calculated the 0th index, we will begin with the 1st index. calculating optimal dp values in a top-down approach for (int a = 1; a < length; a++) { for (int b = 0; b < a; b++) { // Make sure the subsequence is increasing. if (elements[b] < elements[a]) { for (int c = 1; c <= k - 1; c++) { // Proceed if the value has already calculated. if (dp[b][c] != -1) { /* Examine all the subsequences that terminate at any ji and attempt to include the element at index i in them.for a certain length l. For each length, update the maximum value.*/ dp[a][c + 1] = Math.max(dp[a][c + 1], dp[b][c] + elements[a]); } } } } } // The largest value of dp[i][k] for each distinct i would be the ultimate outcome. for (int a = 0; a < length; a++) { if (maxSum < dp[a][k]) maxSum = dp[a][k]; } // The total would be regarded as 0 when there is no feasible subsequence of length k. return (maxSum == -1) ? 0 : maxSum; } public static void main(String args[]) { int length = 10; int k = 4; int[] elements = { 6, 9, 4, 8, 10, 7, 12, 13, 11, 5 }; int maxSum = calculateMaxSumOfIncreasingSubsequence(elements, length, k); System.out.println(maxSum); } }
Output:
44
Complexity analysis:
Time complexity: The time complexity of the program is O(n2 * k).
Space complexity: The space complexity of the program is O(n2)