Maximum Sum Subsequence - C++ Solution

1. Introduction

This blog post delves into a popular problem in dynamic programming: finding the maximum sum of a subsequence where no two elements are adjacent in the given array. This problem is a classic example of optimizing decisions over sequences in C++.

Problem

Given an integer array, the objective is to find the maximum sum of a subsequence where the subsequence contains no elements at adjacent positions.

Example:

Input: [1, 2, 9, 4, 5, 0, 4, 11, 6]

Output: 26

Explanation: The maximum sum is 26, formed by the subsequence [1, 9, 5, 11].

2. Solution Steps

1. Use dynamic programming to build a solution array where each element represents the maximum sum up to that point, without using adjacent elements.

2. Initialize the first two elements of the solution array based on the input array.

3. Iterate through the input array, updating the solution array by choosing the maximum sum possible at each step without including adjacent elements.

4. The last element of the solution array contains the maximum sum of the required subsequence.

3. Code Program

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

int maxSumNoAdjacent(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    if (n == 1) return nums[0];

    vector<int> dp(n);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);

    for (int i = 2; i < n; ++i) {
        dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
    }

    return dp[n - 1];
}

int main() {
    vector<int> nums = {1, 2, 9, 4, 5, 0, 4, 11, 6};
    cout << "Maximum sum of non-adjacent subsequence: " << maxSumNoAdjacent(nums) << endl;
    return 0;
}

Output:

Maximum sum of non-adjacent subsequence: 26

Explanation:

The maxSumNoAdjacent function uses dynamic programming to find the maximum sum of a subsequence with non-adjacent elements. It initializes a DP array with the first two elements' maximum sums. Then, for each element in the input array, it calculates the maximum sum up to that point by considering the maximum of either including the current element and the maximum sum two steps back, or the maximum sum at the previous step (excluding the current element). The last element of the DP array gives the required maximum sum, which is 26 for the given example.