Maximum Sum of Subsequence With Non-adjacent Elements

You are given an array nums consisting of integers. You are also given a 2D array queries, where queries[i] = [pos_i, x_i]. For query i, we first set nums[pos_i] equal to x_i, then we calculate the answer to query i which is the maximum sum of a subsequence of nums where no two adjacent elements are selected. Return the sum of the answers to all queries. Since the final answer may be very large, return it modulo 10^9 + 7. A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements. Example: nums = [3,5,9], queries = [[1,-2],[0,-3]]. Expected output: 21. Explanation: After the 1st query, nums = [3,-2,9] and the maximum sum of a subsequence with non-adjacent elements is 3 + 9 = 12. After the 2nd query, nums = [-3,-2,9] and the maximum sum of a subsequence with non-adjacent elements is 9. Can you provide a C++ solution?

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Naive Solution (Brute Force)
long long solveNaive(vector<int> nums) {
    int n = nums.size();
    long long maxSum = 0;

    for (int i = 0; i < (1 << n); ++i) {
        long long currentSum = 0;
        bool valid = true;
        vector<int> subsequence;

        for (int j = 0; j < n; ++j) {
            if ((i >> j) & 1) {
                subsequence.push_back(j);
            }
        }

        for (size_t k = 0; k < subsequence.size(); ++k) {
            if (k > 0 && subsequence[k] == subsequence[k-1] + 1) {
                valid = false;
                break;
            }
        }

        if (valid) {
            for (int index : subsequence) {
                currentSum += nums[index];
            }
            maxSum = max(maxSum, currentSum);
        }
    }
    return maxSum;
}

// Optimized Solution (Dynamic Programming)
long long solveOptimized(vector<int> nums) {
    int n = nums.size();
    if (n == 0) return 0;

    long long include = nums[0] > 0 ? nums[0] : 0;
    long long exclude = 0;

    for (int i = 1; i < n; ++i) {
        long long newInclude = exclude + (nums[i] > 0 ? nums[i] : 0);
        long long newExclude = max(include, exclude);

        include = newInclude;
        exclude = newExclude;
    }

    return max(include, exclude);
}

int main() {
    vector<int> nums1 = {3, 5, 9};
    vector<pair<int, int>> queries1 = {{1, -2}, {0, -3}};

    long long totalSum1 = 0;
    vector<int> tempNums1 = nums1;
    for (auto& query : queries1) {
        int pos = query.first;
        int x = query.second;
        tempNums1[pos] = x;
        totalSum1 = (totalSum1 + solveOptimized(tempNums1)) % 1000000007;
    }
    cout << "Total Sum for Example 1: " << totalSum1 << endl; // Output: 21

    vector<int> nums2 = {0, -1};
    vector<pair<int, int>> queries2 = {{0, -5}};

    long long totalSum2 = 0;
    vector<int> tempNums2 = nums2;
    for (auto& query : queries2) {
        int pos = query.first;
        int x = query.second;
        tempNums2[pos] = x;
        totalSum2 = (totalSum2 + solveOptimized(tempNums2)) % 1000000007;
    }
    cout << "Total Sum for Example 2: " << totalSum2 << endl; // Output: 0

    return 0;
}

Naive Solution:

The naive solution involves generating all possible subsequences and checking for each subsequence if it satisfies the non-adjacent condition. If it does, calculate the sum of the subsequence and update the maximum sum found so far.

Optimized Solution:

The optimized solution uses dynamic programming to find the maximum sum of a subsequence with no two adjacent elements. We maintain two variables, include and exclude. include stores the maximum sum including the current element, and exclude stores the maximum sum excluding the current element. At each step, we update these variables to find the maximum possible sum.

Big(O) Run-time Analysis:

• Naive Solution: The time complexity is O(2^n * n), where n is the size of the input array. This is because we generate 2^n possible subsequences, and for each subsequence, we iterate through it to check for the non-adjacent condition and calculate the sum.
• Optimized Solution: The time complexity is O(n), where n is the size of the input array. This is because we iterate through the array once, updating the include and exclude variables at each step.

Big(O) Space Usage Analysis:

• Naive Solution: The space complexity is O(n) in the worst case, as we store the subsequence indices in a vector.
• Optimized Solution: The space complexity is O(1), as we only use a constant amount of extra space to store the include and exclude variables.

Edge Cases:

1. Empty Array: If the input array is empty, the maximum sum is 0.
2. All Negative Numbers: If all numbers in the array are negative, the maximum sum is 0 (choosing an empty subsequence).
3. Single Element: If the array has only one element, the maximum sum is the element itself if it's positive, or 0 if it's negative.
4. Large Numbers: If the numbers are large, we need to use long long to prevent overflow.
5. Zeroes in the Array: Zeroes don't affect the non-adjacency condition, so they can be included or excluded as needed to maximize the sum.