3165. Maximum Sum of Subsequence With Non-adjacent Elements LeetCode Solution

In this guide, you will get 3165. Maximum Sum of Subsequence With Non-adjacent Elements LeetCode Solution with the best time and space complexity. The solution to Maximum Sum of Subsequence With Non-adjacent Elements problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximum Sum of Subsequence With Non-adjacent Elements solution in C++
4. Maximum Sum of Subsequence With Non-adjacent Elements solution in Java
5. Maximum Sum of Subsequence With Non-adjacent Elements solution in Python
6. Additional Resources

Problem Statement of 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] = [posi, xi].
For query i, we first set nums[posi] equal to xi, 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 109 + 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 1:

Input: nums = [3,5,9], queries = [[1,-2],[0,-3]]
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.

Example 2:

Input: nums = [0,-1], queries = [[0,-5]]
Output: 0
Explanation:
After the 1st query, nums = [-5,-1] and the maximum sum of a subsequence with non-adjacent elements is 0 (choosing an empty subsequence).

Constraints:

1 <= nums.length <= 5 * 104
-105 <= nums[i] <= 105
1 <= queries.length <= 5 * 104
queries[i] == [posi, xi]
0 <= posi <= nums.length – 1
-105 <= xi <= 105

Complexity Analysis

• Time Complexity: O(n + q\log n)
• Space Complexity: O(n)

3165. Maximum Sum of Subsequence With Non-adjacent Elements LeetCode Solution in C++

using NodeType = array<array<int, 2>, 2>;

class SegmentTree {
 public:
  explicit SegmentTree(const vector<int>& nums) : n(nums.size()), tree(4 * n) {
    build(nums, 0, 0, n - 1);
  }

  // Updates nums[i] to val.
  void update(int i, int val) {
    update(0, 0, n - 1, i, val);
  }

  // Returns the four values of the range query from nums[i..j].
  //
  // The four values are:
  //   1. nums[i] is not selected, nums[j] is not selected
  //   2. nums[i] is not selected, nums[j] is selected
  //   3. nums[i] is selected, nums[j] is not selected
  //   4. nums[i] is selected, nums[j] is selected
  NodeType query(int i, int j) const {
    return query(0, 0, n - 1, i, j);
  }

 private:
  static constexpr int kInf = 1'000'000'000;
  static constexpr NodeType kDefaultNode = {{{-kInf, -kInf}, {-kInf, -kInf}}};
  const int n;  // the size of the input array
  // tree[i][l][r] := the value of the i-th node, where `l` and `r` represent if
  // the leftmost or rightmost element is selected, respectively
  vector<NodeType> tree;

  void build(const vector<int>& nums, int treeIndex, int lo, int hi) {
    if (lo == hi) {
      tree[treeIndex] = {{{0, -kInf}, {-kInf, nums[lo]}}};
      return;
    }
    const int mid = (lo + hi) / 2;
    build(nums, 2 * treeIndex + 1, lo, mid);
    build(nums, 2 * treeIndex + 2, mid + 1, hi);
    tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
  }

  void update(int treeIndex, int lo, int hi, int i, int val) {
    if (lo == hi) {
      tree[treeIndex] = {{{0, -kInf}, {-kInf, val}}};
      return;
    }
    const int mid = (lo + hi) / 2;
    if (i <= mid)
      update(2 * treeIndex + 1, lo, mid, i, val);
    else
      update(2 * treeIndex + 2, mid + 1, hi, i, val);
    tree[treeIndex] = merge(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
  }

  NodeType query(int treeIndex, int lo, int hi, int i, int j) const {
    if (i <= lo && hi <= j)  // [lo, hi] lies completely inside [i, j].
      return tree[treeIndex];
    if (j < lo || hi < i)  // [lo, hi] lies completely outside [i, j].
      return kDefaultNode;
    const int mid = (lo + hi) / 2;
    return merge(query(2 * treeIndex + 1, lo, mid, i, j),
                 query(2 * treeIndex + 2, mid + 1, hi, i, j));
  }

  // Merges the result of the left node and the right node.
  NodeType merge(const NodeType& a, const NodeType& b) const {
    NodeType node = {{{0, 0}, {0, 0}}};
    for (int l = 0; l < 2; ++l)
      for (int r = 0; r < 2; ++r)
        node[l][r] =
            max({a[l][0] + b[0][r], a[l][0] + b[1][r], a[l][1] + b[0][r]});
    return node;
  }
};

class Solution {
 public:
  int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    int ans = 0;
    SegmentTree tree(nums);

    for (const vector<int>& query : queries) {
      const int pos = query[0];
      const int x = query[1];
      tree.update(pos, x);
      NodeType res = tree.query(0, n - 1);
      ans = (ans + static_cast<long>(
                       max({res[0][0], res[0][1], res[1][0], res[1][1]}))) %
            kMod;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3165. Maximum Sum of Subsequence With Non-adjacent Elements LeetCode Solution in Java

N/A
// code provided by PROGIEZ

3165. Maximum Sum of Subsequence With Non-adjacent Elements LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.