# 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(n^{2 * }k).

**Space complexity: **The space complexity of the program is O(n^{2})