Implement the solution to the Maximum Sum Increasing Subsequence problem using dynamic programming.?

The Maximum Sum Increasing Subsequence (MSIS) problem is to find the maximum sum subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. This problem can be solved using dynamic programming.

Let’s consider the following example sequence:

sequence = [1, 101, 2, 3, 100, 4, 5]

To solve this problem, we will use an array ‘msis‘ of size ‘n‘ where ‘n‘ is the length of the sequence. The ‘i‘th index of ‘msis‘ will store the maximum sum of increasing subsequence ending at ‘i‘.

We can start by initializing all elements of ‘msis‘ to their corresponding values in the sequence, since each element can be considered as a subsequence in itself.

msis = [1, 101, 2, 3, 100, 4, 5]

We can then iterate through the array ‘msis‘ starting from the second element, and for each ‘i‘th element, we can find the maximum sum of increasing subsequence ending at ‘i‘ by iterating through all elements before ‘i‘ and finding the maximum value of ‘msis[j] + sequence[i]‘ where ‘j‘ is less than ‘i‘ and ‘sequence[j]‘ is less than ‘sequence[i]‘.

for i in range(1, n):
    for j in range(i):
        if sequence[j] < sequence[i]:
            msis[i] = max(msis[i], msis[j] + sequence[i])

After iterating through the entire array ‘msis‘, the maximum sum of increasing subsequence in the original sequence can be found by finding the maximum element in the ‘msis‘ array.

max_sum = max(msis)

The complete implementation of the MSIS problem in Java is as follows:

public static int maxSumIncreasingSubsequence(int[] sequence) {
    int n = sequence.length;
    int[] msis = new int[n];
    for (int i = 0; i < n; i++) {
        msis[i] = sequence[i];
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (sequence[j] < sequence[i]) {
                msis[i] = Math.max(msis[i], msis[j] + sequence[i]);
            }
        }
    }
    int maxSum = Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        if (msis[i] > maxSum) {
            maxSum = msis[i];
        }
    }
    return maxSum;
}

For the example sequence ‘[1, 101, 2, 3, 100, 4, 5]‘, the maximum sum of increasing subsequence is ‘106‘ which can be obtained by the subsequence ‘[1, 2, 3, 100]‘.