3165. Maximum Sum of Subsequence With Non-adjacent Elements

HardSegment TreeArrayDivide and ConquerDynamic Programming

Problem Description

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 each query i, you first set nums[pos_i] to x_i, then calculate the answer to that query 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 elements without changing the order of the remaining elements.

Intuition

The problem requires calculating the maximum sum of a subsequence from an array nums after multiple updates, with the condition that no two adjacent elements are selected. This indicates a dynamic programming problem, but given the nature of the queries, a data structure that allows both updates and queries efficiently is needed.

A dynamic approach using a segment tree is suitable here because it efficiently handles point updates and range maximum queries. The core idea is to maintain several states in each node of the segment tree that keep track of possible maximum sums:

s00: Maximum sum in subsequences that do not include the left and right endpoints.
s01: Maximum sum in subsequences that do not include the left but can include the right endpoint.
s10: Maximum sum in subsequences that can include the left but not the right endpoint.
s11: Maximum sum in subsequences that can include both the left and right endpoints.

By maintaining these states, the segment tree can dynamically update and fetch the required maximum sum efficiently. Each query modifies a position in nums and then uses the segment tree to calculate the maximum sum subsequence for the current array configuration, accumulating the results for all queries. This approach ensures that even with multiple updates, the maximum sum subsequence can be calculated in logarithmic time due to the properties of the segment tree.

Learn more about Segment Tree, Divide and Conquer and Dynamic Programming patterns.

Solution Approach

The solution employs a [Segment Tree](/problems/segment_tree_intro) data structure to manage and optimize the queries and updates performed on the array nums. This approach allows efficient handling of point updates and range queries necessary for the problem constraints.

Step-by-Step Implementation

Segment Tree Node Definition:
- Each node in the segment tree maintains four states to track different possible maximum sums:
  - s00: Maximum sum excluding both left and right endpoints.
  - s01: Maximum sum excluding the left, but including the right endpoint.
  - s10: Maximum sum including the left, but excluding the right endpoint.
  - s11: Maximum sum including both the left and right endpoints.
Tree Construction:
- The segment tree is constructed recursively. For each node, its children (left and right subtrees) are initialized first, ensuring a bottom-up construction.
- During this construction phase, the build function divides the tree recursively until each element of the array nums has a corresponding leaf in the tree.
Point Updates:
- When processing each query [pos_i, x_i], the segment tree's modify function updates the respective node. It assigns the new value x_i to nums[pos_i] and updates the node values accordingly.
- This update involves recalculating the state values for both the individual node and propagating necessary changes upwards through the pushup function.
Range Query:
- To derive the maximum sum subsequence for the current configuration of nums, we perform a query across the entire range of the array.
- The query function traverses nodes that fall within the queried range, fetching the s11 state, which represents the desired maximum sum subsequence under the current configuration.
Accumulating Results:
- After processing each query, the obtained result (maximum sum for the current configuration) is added to a total sum of all results, which is then returned modulo (10^9 + 7) for correctness and to handle potential overflow.

This segment tree approach efficiently manages both updates and queries, ensuring the solution remains optimal as it scales with the input size.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using a segment tree.

Example:

Input nums: [2, 3, 1]
Queries: [[0, 4], [1, 5]]

Process:

Initial Setup:
- The segment tree is built using the initial array [2, 3, 1]. Each element is a leaf node, and internal nodes track the maximum sum of subsequences with the described states (s00, s01, s10, s11).
Processing Query [0, 4]:
- Update: Set nums[0] to 4. Array becomes [4, 3, 1].
- Recalculate Segment Tree:
  - Update the corresponding segment tree node for index 0.
  - Update the states using the child nodes to propagate changes up the tree.
- Calculate Maximum Sum:
  - Perform a range query on the updated array [4, 3, 1].
  - The s11 state of the root node provides the maximum sum: for [4, 3, 1], the non-adjacent maximum sum is 4 + 1 = 5.
Processing Query [1, 5]:
- Update: Set nums[1] to 5. Array becomes [4, 5, 1].
- Recalculate Segment Tree:
  - Modify the node for index 1 and propagate changes with the pushup function to maintain accurate states.
- Calculate Maximum Sum:
  - Execute a range query on the updated array [4, 5, 1].
  - Maximum sum for non-adjacent elements: 4 + 1 = 5.
Accumulating Results:
- The results from each query are accumulated: 5 (from first query) + 5 (from second query) = 10.
- Return 10 % (10^9 + 7) = 10 as the final answer.

Thus, through efficient updates and queries with the segment tree, the solution quickly computes the desired result even with multiple dynamic changes to the array.

Solution Implementation

1from typing import List
2
3def max(a: int, b: int) -> int:
4    # Returns the maximum of two numbers
5    return a if a > b else b
6
7class Node:
8    # Define the slots for the Node class for memory optimization
9    __slots__ = "l", "r", "s00", "s01", "s10", "s11"
10
11    def __init__(self, l: int, r: int):
12        # Initialize Node with left, right bounds and segment tree values
13        self.l = l  # Left index
14        self.r = r  # Right index
15        self.s00 = 0  # Segment value s00
16        self.s01 = 0  # Segment value s01
17        self.s10 = 0  # Segment value s10
18        self.s11 = 0  # Segment value s11
19
20class SegmentTree:
21    # Define the slots for the SegmentTree class for memory optimization
22    __slots__ = "tr"
23
24    def __init__(self, n: int):
25        # Initialize the segment tree with size 4 * n (standard for segment trees)
26        self.tr: List[Node | None] = [None] * (n << 2)
27        self.build(1, 1, n)  # Build the tree starting from index 1 covering range 1 to n
28
29    def build(self, u: int, l: int, r: int):
30        # Recursive method to build the segment tree
31        self.tr[u] = Node(l, r)  # Initialize the node at index u
32        if l == r:
33            # If we are at a leaf node, return
34            return
35        mid = (l + r) >> 1  # Calculate mid point
36        self.build(u << 1, l, mid)  # Build left subtree
37        self.build(u << 1 | 1, mid + 1, r)  # Build right subtree
38
39    def query(self, u: int, l: int, r: int) -> int:
40        # Retrieve the maximum sum subsequence for a given range [l, r]
41        if self.tr[u].l >= l and self.tr[u].r <= r:
42            # If the current node's range is completely within the query range
43            return self.tr[u].s11
44        mid = (self.tr[u].l + self.tr[u].r) >> 1
45        ans = 0
46        if r <= mid:
47            # If the query range is entirely in the left subtree
48            ans = self.query(u << 1, l, r)
49        if l > mid:
50            # If the query range is entirely in the right subtree
51            ans = max(ans, self.query(u << 1 | 1, l, r))
52        return ans
53
54    def pushup(self, u: int):
55        # Method to update values of the current node using its children
56        left, right = self.tr[u << 1], self.tr[u << 1 | 1]
57        self.tr[u].s00 = max(left.s00 + right.s10, left.s01 + right.s00)
58        self.tr[u].s01 = max(left.s00 + right.s11, left.s01 + right.s01)
59        self.tr[u].s10 = max(left.s10 + right.s10, left.s11 + right.s00)
60        self.tr[u].s11 = max(left.s10 + right.s11, left.s11 + right.s01)
61
62    def modify(self, u: int, x: int, v: int):
63        # Update the value at position x with value v in the segment tree
64        if self.tr[u].l == self.tr[u].r:
65            # If we are at the leaf node for the index to modify
66            self.tr[u].s11 = max(0, v)  # Update value ensuring non-negative
67            return
68        mid = (self.tr[u].l + self.tr[u].r) >> 1
69        if x <= mid:
70            # If x is in the left subtree
71            self.modify(u << 1, x, v)
72        else:
73            # If x is in the right subtree
74            self.modify(u << 1 | 1, x, v)
75        self.pushup(u)  # Update the current node
76
77class Solution:
78    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
79        # Initialize the segment tree with the number of elements in nums
80        n = len(nums)
81        tree = SegmentTree(n)
82
83        # Initially populate the segment tree with the nums values
84        for i, x in enumerate(nums, 1):
85            tree.modify(1, i, x)
86
87        ans = 0
88        mod = 10**9 + 7
89
90        # Process each query to update the tree and get the maximum sum
91        for i, x in queries:
92            tree.modify(1, i + 1, x)  # Update the value at index i
93            ans = (ans + tree.query(1, 1, n)) % mod  # Get max for full array
94
95        return ans
96

1// Class to represent a node in the segment tree
2class Node {
3    int left, right; // Range this node covers
4    long s00, s01, s10, s11; // Segment values for different states
5
6    // Constructor to initialize a node with given range boundaries
7    Node(int left, int right) {
8        this.left = left;
9        this.right = right;
10        this.s00 = this.s01 = this.s10 = this.s11 = 0;
11    }
12}
13
14// Class to represent a segment tree
15class SegmentTree {
16    Node[] tree; // Array to store nodes of the segment tree
17
18    // Constructor to initialize the segment tree with given size
19    SegmentTree(int n) {
20        tree = new Node[n * 4]; // Size is 4 times the number of elements
21        build(1, 1, n); // Build the tree starting from root node
22    }
23
24    // Method to build the segment tree
25    void build(int u, int left, int right) {
26        tree[u] = new Node(left, right); // Initialize node with given range
27
28        // If leaf node, return as there is nothing more to divide
29        if (left == right) {
30            return;
31        }
32
33        int mid = (left + right) >> 1; // Calculate midpoint to divide ranges
34        build(u << 1, left, mid); // Recursively build left subtree
35        build(u << 1 | 1, mid + 1, right); // Recursively build right subtree
36    }
37
38    // Method to query the segment tree for maximum sum in a range
39    long query(int u, int left, int right) {
40        // If current node's range is within the query range, return stored value
41        if (tree[u].left >= left && tree[u].right <= right) {
42            return tree[u].s11;
43        }
44
45        long answer = 0;
46        int mid = (tree[u].left + tree[u].right) >> 1; // Determine midpoint
47
48        // Check which side of the tree to query
49        if (right <= mid) {
50            answer = query(u << 1, left, right); // Query left subtree
51        }
52        if (left > mid) {
53            answer = Math.max(answer, query(u << 1 | 1, left, right)); // Query right subtree
54        }
55
56        return answer; // Return the maximum result
57    }
58
59    // Method to update the parent node with new information
60    void pushup(int u) {
61        Node leftNode = tree[u << 1]; // Get left child node
62        Node rightNode = tree[u << 1 | 1]; // Get right child node
63
64        // Update current node state based on children
65        tree[u].s00 = Math.max(leftNode.s00 + rightNode.s10, leftNode.s01 + rightNode.s00);
66        tree[u].s01 = Math.max(leftNode.s00 + rightNode.s11, leftNode.s01 + rightNode.s01);
67        tree[u].s10 = Math.max(leftNode.s10 + rightNode.s10, leftNode.s11 + rightNode.s00);
68        tree[u].s11 = Math.max(leftNode.s10 + rightNode.s11, leftNode.s11 + rightNode.s01);
69    }
70
71    // Method to modify a specific position in the segment tree
72    void modify(int u, int x, int value) {
73        // If leaf node, set the value
74        if (tree[u].left == tree[u].right) {
75            tree[u].s11 = Math.max(0, value);
76            return;
77        }
78
79        int mid = (tree[u].left + tree[u].right) >> 1; // Find midpoint
80
81        // Update appropriate child node
82        if (x <= mid) {
83            modify(u << 1, x, value);
84        } else {
85            modify(u << 1 | 1, x, value);
86        }
87
88        pushup(u); // Update current node based on modifications to children
89    }
90}
91
92// Solution class to handle the main logic for maximum sum subsequence problem
93class Solution {
94    public int maximumSumSubsequence(int[] nums, int[][] queries) {
95        int n = nums.length; // Get length of input number sequence
96        SegmentTree tree = new SegmentTree(n); // Initialize segment tree
97
98        // Populate segment tree with initial values from nums
99        for (int i = 0; i < n; ++i) {
100            tree.modify(1, i + 1, nums[i]);
101        }
102
103        long result = 0;
104        final int mod = (int) 1e9 + 7; // Define modulo constant for result
105
106        // Process each query and compute total maximum sum
107        for (int[] query : queries) {
108            tree.modify(1, query[0] + 1, query[1]);
109            result = (result + tree.query(1, 1, n)) % mod;
110        }
111
112        return (int) result; // Return final result as integer
113    }
114}
115

1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6// Node class representing each segment in the segment tree
7class Node {
8public:
9    // Range it represents
10    int l, r;
11    // Segment sums for different combinations of subsequences
12    long long s00, s01, s10, s11;
13
14    // Constructor to initialize the node with a given range
15    Node(int l, int r)
16        : l(l)
17        , r(r)
18        , s00(0)
19        , s01(0)
20        , s10(0)
21        , s11(0) {}
22};
23
24// Segment tree class for efficient range query and updates
25class SegmentTree {
26public:
27    vector<Node*> tree; // Vector to hold pointers to Node objects
28
29    // Constructor to initialize the segment tree with `n` leaf nodes
30    SegmentTree(int n)
31        : tree(n * 4) { // Four times the number of elements for safe allocation
32        build(1, 1, n); // Build the tree from index 1 to n
33    }
34
35    // Build the tree recursively
36    void build(int index, int left, int right) {
37        tree[index] = new Node(left, right);
38        if (left == right) {
39            return; // Leaf node; no further partition
40        }
41        int mid = (left + right) / 2;
42        build(index * 2, left, mid);
43        build(index * 2 + 1, mid + 1, right);
44    }
45
46    // Query the maximum sum subsequence within a range
47    long long query(int index, int left, int right) {
48        if (tree[index]->l >= left && tree[index]->r <= right) {
49            return tree[index]->s11; // Return sum for the exact range
50        }
51        int mid = (tree[index]->l + tree[index]->r) / 2;
52        long long maxSubsequenceSum = 0;
53        if (right <= mid) {
54            maxSubsequenceSum = query(index * 2, left, right);
55        }
56        if (left > mid) {
57            maxSubsequenceSum = max(maxSubsequenceSum, query(index * 2 + 1, left, right));
58        }
59        return maxSubsequenceSum;
60    }
61
62    // Update the current node using its children nodes
63    void pushup(int index) {
64        Node* leftChild = tree[index * 2];
65        Node* rightChild = tree[index * 2 + 1];
66        tree[index]->s00 = max(leftChild->s00 + rightChild->s10, leftChild->s01 + rightChild->s00);
67        tree[index]->s01 = max(leftChild->s00 + rightChild->s11, leftChild->s01 + rightChild->s01);
68        tree[index]->s10 = max(leftChild->s10 + rightChild->s10, leftChild->s11 + rightChild->s00);
69        tree[index]->s11 = max(leftChild->s10 + rightChild->s11, leftChild->s11 + rightChild->s01);
70    }
71
72    // Modify the tree to update the value at position `x` with `v`
73    void modify(int index, int pos, int value) {
74        if (tree[index]->l == tree[index]->r) {
75            tree[index]->s11 = max(0LL, static_cast<long long>(value));
76            return;
77        }
78        int mid = (tree[index]->l + tree[index]->r) / 2;
79        if (pos <= mid) {
80            modify(index * 2, pos, value);
81        } else {
82            modify(index * 2 + 1, pos, value);
83        }
84        pushup(index); // Update the current node after modification
85    }
86
87    // Destructor to free up the dynamically allocated memory
88    ~SegmentTree() {
89        for (auto node : tree) {
90            delete node;
91        }
92    }
93};
94
95// Solution class implementing the solution to the problem
96class Solution {
97public:
98    // Function to find the maximum sum of subsequences based on given queries
99    int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {
100        int n = nums.size();
101        SegmentTree segmentTree(n);
102
103        // Initialize the segment tree with the given nums array
104        for (int i = 0; i < n; ++i) {
105            segmentTree.modify(1, i + 1, nums[i]);
106        }
107
108        long long result = 0; // To store the result of the maximum sum subsequence
109        const int MODULO = 1e9 + 7;
110
111        // Process each query and update the tree and result
112        for (const auto& query : queries) {
113            segmentTree.modify(1, query[0] + 1, query[1]);
114            result = (result + segmentTree.query(1, 1, n)) % MODULO;
115        }
116        return static_cast<int>(result);
117    }
118};
119

1// Define a Node structure to represent each segment in the segment tree
2interface Node {
3    l: number;
4    r: number;
5    s00: number;
6    s01: number;
7    s10: number;
8    s11: number;
9}
10
11// Array to store the nodes of the segment tree
12let tr: Node[];
13
14// Initialize the segment tree with a given size
15function SegmentTree(n: number) {
16    tr = Array(n * 4);
17    build(1, 1, n);
18}
19
20// Recursively build the segment tree
21function build(u: number, l: number, r: number) {
22    tr[u] = { l, r, s00: 0, s01: 0, s10: 0, s11: 0 };
23    if (l === r) {
24        return; // Base case: single element segment
25    }
26    const mid = (l + r) >> 1; // Calculate the mid-point
27    build(u << 1, l, mid); // Build left child
28    build((u << 1) | 1, mid + 1, r); // Build right child
29}
30
31// Query the maximum sum subsequence in the range [l, r]
32function query(u: number, l: number, r: number): number {
33    if (tr[u].l >= l && tr[u].r <= r) {
34        return tr[u].s11; // Node range is completely within query range
35    }
36    const mid = (tr[u].l + tr[u].r) >> 1;
37    let ans = 0;
38    if (r <= mid) {
39        ans = query(u << 1, l, r); // Query left child
40    }
41    if (l > mid) {
42        ans = Math.max(ans, query((u << 1) | 1, l, r)); // Query right child
43    }
44    return ans;
45}
46
47// Update the segment tree values after a modification
48function pushup(u: number) {
49    const left = tr[u << 1];
50    const right = tr[(u << 1) | 1];
51    tr[u].s00 = Math.max(left.s00 + right.s10, left.s01 + right.s00);
52    tr[u].s01 = Math.max(left.s00 + right.s11, left.s01 + right.s01);
53    tr[u].s10 = Math.max(left.s10 + right.s10, left.s11 + right.s00);
54    tr[u].s11 = Math.max(left.s10 + right.s11, left.s11 + right.s01);
55}
56
57// Modify the segment tree at position x with a new value v
58function modify(u: number, x: number, v: number) {
59    if (tr[u].l === tr[u].r) {
60        tr[u].s11 = Math.max(0, v); // Update leaf node
61        return;
62    }
63    const mid = (tr[u].l + tr[u].r) >> 1;
64    if (x <= mid) {
65        modify(u << 1, x, v); // Modify left child
66    } else {
67        modify((u << 1) | 1, x, v); // Modify right child
68    }
69    pushup(u); // Update current node values
70}
71
72// Function to compute the maximum sum subsequence after a series of updates
73function maximumSumSubsequence(nums: number[], queries: number[][]): number {
74    const n = nums.length;
75    SegmentTree(n);
76    for (let i = 0; i < n; i++) {
77        modify(1, i + 1, nums[i]); // Initialize segment tree with initial values
78    }
79    let ans = 0;
80    const mod = 1e9 + 7;
81    for (const [i, x] of queries) {
82        modify(1, i + 1, x); // Process each query
83        ans = (ans + query(1, 1, n)) % mod; // Update answer
84    }
85    return ans; // Return the final answer
86}
87

Time and Space Complexity

The time complexity of the code is O((n + q) * log n), where n is the length of the array nums, and q is the number of queries. This is because building the segment tree takes O(n * log n), and each query and modification operation takes O(log n). With q queries and potential modifications, the overall complexity amounts to O((n + q) * log n).

The space complexity of the code is O(n). This is attributed to the segment tree structure, which requires space proportional to 4n (or O(n)) to store its nodes.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: