# 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 j\i 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)