Maximum Sum Increasing Subsequence in C++

In this problem, we are given an array arr[] of N integers and two index values x and y. Our task is to create a program to find the Maximum sum increasing subsequence from a prefix and a given element after prefix is must in C++.

Problem Description

We will find the maximum sum of increasing sequence till index x and including the element at index y.

Let’s take an example to understand the problem,

Input

arr[] = {1, 5, 9, 131, 6, 100, 11, 215}, x = 4, y = 6

Output

26

Explanation

We will take the subsequence till index 3 and then at last include arr[6] = 11.

The subsequence is {1, 5, 9, 11}. Sum = 1+5+9+11 = 26

Solution Approach

A simple approach is creating a new array till x index and then adding the element at index y at the end. Then calculate all increasing subsequences and then discard all that cannot include the element arr[y], and find the maxSum.

One more effective approach to solve the problem is using a dynamic programming approach. The idea is to create a 2-D array DP[][], and store the maximum sum of increasing subsequence. The value at DP[x][y] will give the max sum till index x including element arr[y].

Example

Program to illustrate the working of our solution,

 Live Demo

#include <iostream>
using namespace std;
int DP[100][100];
void preCalcMaxSum(int arr[], int N){
   for (int i = 0; i < N; i++) {
      if (arr[i] > arr[0])
         DP[0][i] = arr[i] + arr[0];
      else
         DP[0][i] = arr[i];
   }
   for (int i = 1; i < N; i++) {
      for (int j = 0; j < N; j++) {
         if (arr[j] > arr[i] && j > i) {
            if (DP[i - 1][i] + arr[j] > DP[i - 1][j])
               DP[i][j] = DP[i - 1][i] + arr[j];
            else
               DP[i][j] = DP[i - 1][j];
         }
         else
            DP[i][j] = DP[i - 1][j];
      }
   }
}
int main() {
   int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
   int N = sizeof(arr) / sizeof(arr[0]);
   int x = 4, y = 6;
   preCalcMaxSum(arr, N);
   cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
   cout<<DP[x][y];
   return 0;
}

Output

The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26

An efficient approach is using to find the maximum sum of increasing subsequence till index x in such a way that the largest element of the sequence is less than element at index y. For this we will again use the dynamic programming approach.

Example

Program to illustrate the working of our solution,

 Live Demo

#include <iostream>
using namespace std;
int calcMaxSum(int arr[], int n, int x, int y){
   int DP[x] = {0};
   int maxSum = -1;
   for (int i = 0; i <= x; i++)
      DP[i] = arr[i];
   for (int i = 0; i <= x; i++) {
      if (arr[i] >= arr[y]) {
         continue;
      }
      for (int j = 0; j < i; j++) {
         if (arr[i] > arr[j])
            DP[i] += arr[j];
            maxSum = max(maxSum, DP[i]);
      }
   }
   if (maxSum == -1) {
      return arr[y];
   }
   return maxSum + arr[y];
}
int main(){
   int arr[] = {1, 5, 9, 131, 6, 100, 11, 215};
   int N = sizeof(arr) / sizeof(arr[0]);
   int x = 4, y = 6;
   cout<<"The maximum sum increasing subsequence from a prefix and a given element after prefix is must is ";
   cout<<calcMaxSum(arr, N, x, y);
   return 0;
}

Output

The maximum sum increasing subsequence from a prefix and a given element after prefix is must is 26