Max Sum Increasing Subsequence - C++ Solution

1. Introduction

This blog post focuses on a dynamic programming problem: finding the maximum sum increasing subsequence in a given sequence. This problem is about identifying a subsequence of elements that are in ascending order and whose sum is the highest possible.

Problem

Given a sequence of integers, the task is to find a subsequence such that the elements are sorted in ascending order and the sum of the subsequence is maximized.

Examples:

- Input: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11]

Output: 34

- Input: [-4, -3, -2, -1]

Output: 0

2. Solution Steps

1. Use dynamic programming to build a solution array where each element represents the maximum sum possible up to that point with an increasing subsequence.

2. Initialize the solution array with the values of the original array.

3. Iterate through the array and for each element, find the maximum sum of the increasing subsequence that can be formed including that element.

4. Update the solution array based on the maximum sum found.

5. The maximum value in the solution array is the answer.

3. Code Program

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSumIncreasingSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(nums.begin(), nums.end());
    int maxSum = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], nums[i] + dp[j]);
            }
        }
        maxSum = max(maxSum, dp[i]);
    }

    return maxSum;
}

int main() {
    vector<int> nums = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11};
    cout << "Maximum sum increasing subsequence: " << maxSumIncreasingSubsequence(nums) << endl;
    return 0;
}

Output:

Maximum sum increasing subsequence: 34

Explanation:

The maxSumIncreasingSubsequence function iterates through the given sequence and calculates the maximum sum of an increasing subsequence that ends with each element of the array. It maintains an array dp where dp[i] represents the maximum sum of the increasing subsequence ending with nums[i]. By comparing the current element with previous elements and updating dp accordingly, the function determines the maximum sum possible. The final answer is the largest value in the dp array, which is 34 for the given example.