LeetCode Problem 3165

Difficulty: 🔴 Hard
Topics: Array, Divide and Conquer, Dynamic Programming, Segment Tree

Solution

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

Problem Understanding

This problem asks us to process a sequence of update queries on an array. After each update, we must compute the maximum possible sum of a subsequence where no two selected elements are adjacent in the array.

The key detail is that the subsequence does not need to be contiguous. We may choose any set of indices as long as no two chosen indices are neighbors. This is the classic "House Robber" style constraint.

For each query:

1. Update nums[posi] = xi
2. Compute the maximum non-adjacent subsequence sum
3. Add that result to a running total

Finally, return the total modulo 10^9 + 7.

Consider the first example:

nums = [3,5,9]
queries = [[1,-2],[0,-3]]

After the first update:

[3,-2,9]

The best valid subsequence is:

3 + 9 = 12

After the second update:

[-3,-2,9]

The best valid subsequence is:

9

The final answer is:

12 + 9 = 21

The constraints are large:

• n <= 5 * 10^4
• queries.length <= 5 * 10^4

A naive recomputation after every query would be far too slow. If we recomputed the dynamic programming solution from scratch after every update, we would need O(n) work per query, leading to O(n * q) complexity, which could reach 2.5 * 10^9 operations.

Another important detail is that the empty subsequence is allowed. This means the answer is never negative. If all elements are negative, the optimal choice is to select nothing, giving sum 0.

Important edge cases include:

• Arrays containing all negative numbers
• Arrays with only one element
• Repeated updates to the same position
• Large positive and negative values mixed together
• Updates that drastically change the optimal subsequence structure

These cases make careful state management essential.

Approaches

Brute Force Approach

The most direct approach is to process each query independently.

After every update:

1. Modify the array
2. Run the standard House Robber dynamic programming algorithm over the entire array
3. Add the result to the final answer

The classic DP relation is:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

This correctly computes the maximum non-adjacent subsequence sum because for every position we either:

• Skip the current element
• Take the current element and skip the previous one

This approach is correct, but too slow.

If each query requires O(n) work, then with 5 * 10^4 queries and 5 * 10^4 elements, the total complexity becomes:

O(n * q)

which is infeasible.

Optimal Approach

The key observation is that a single update only changes one position, but recomputing the entire DP is wasteful.

We need a data structure that supports:

• Point updates
• Fast recomputation of the global DP answer

This naturally suggests a segment tree.

The challenge is that the House Robber DP depends on adjacency relationships. To merge two segments correctly, we must know whether the endpoints are selected.

For every segment, we maintain four DP states:

dp[left_selected][right_selected]

Each state represents the maximum subsequence sum for that segment under fixed boundary conditions.

When merging two child segments:

• The right endpoint of the left child
• The left endpoint of the right child

cannot both be selected simultaneously because they become adjacent.

This allows us to combine segments efficiently in O(1) per merge.

Since segment tree updates require O(log n) merges, each query can be processed in O(log n) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * q)	O(n)	Recompute House Robber DP after every update
Optimal	O(q log n)	O(n)	Segment tree with DP state transitions

Algorithm Walkthrough

Segment State Definition

For each segment, we store four values:

State	Meaning
s00	Left endpoint not selected, right endpoint not selected
s01	Left endpoint not selected, right endpoint selected
s10	Left endpoint selected, right endpoint not selected
s11	Left endpoint selected, right endpoint selected

These states fully describe how the segment interacts with neighboring segments.

Leaf Node Initialization

For a single element x:

• If we do not select it, sum is 0
• If we select it, sum is max(0, x)

So:

s00 = 0
s11 = max(0, x)
s01 = s10 = -infinity

The mixed states are impossible for a single element because the left and right endpoints are the same element.

Merge Operation

Suppose we merge:

left segment + right segment

We try all valid combinations of states.

The only invalid combination is:

left.right_selected == 1
and
right.left_selected == 1

because those endpoints become adjacent.

For every valid pair of states:

new_sum = left_state + right_state

We update the corresponding merged boundary state.

Processing Queries

For every query:

1. Update the leaf node corresponding to pos
2. Recompute affected segment tree nodes upward
3. The root stores the answer for the entire array
4. Add the root maximum to the global total

Why it works

The segment tree stores complete boundary information for every segment. When two segments are merged, the only adjacency conflict occurs at the shared boundary between them. By explicitly tracking whether endpoints are selected, every valid subsequence configuration is represented exactly once.

Because each merge preserves correctness, the root node always contains the optimal non-adjacent subsequence sum for the entire array.

Python Solution

from typing import List

class Solution:
    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
        MOD = 10**9 + 7
        NEG_INF = float("-inf")

        class Node:
            def __init__(self):
                self.dp = [[NEG_INF] * 2 for _ in range(2)]

        n = len(nums)
        tree = [Node() for _ in range(4 * n)]

        def make_leaf(value: int) -> Node:
            node = Node()
            node.dp[0][0] = 0
            node.dp[1][1] = max(0, value)
            return node

        def merge(left: Node, right: Node) -> Node:
            res = Node()

            for l_start in range(2):
                for l_end in range(2):
                    if left.dp[l_start][l_end] == NEG_INF:
                        continue

                    for r_start in range(2):
                        for r_end in range(2):
                            if right.dp[r_start][r_end] == NEG_INF:
                                continue

                            if l_end == 1 and r_start == 1:
                                continue

                            value = (
                                left.dp[l_start][l_end]
                                + right.dp[r_start][r_end]
                            )

                            res.dp[l_start][r_end] = max(
                                res.dp[l_start][r_end],
                                value
                            )

            return res

        def build(index: int, left: int, right: int) -> None:
            if left == right:
                tree[index] = make_leaf(nums[left])
                return

            mid = (left + right) // 2

            build(index * 2, left, mid)
            build(index * 2 + 1, mid + 1, right)

            tree[index] = merge(
                tree[index * 2],
                tree[index * 2 + 1]
            )

        def update(
            index: int,
            left: int,
            right: int,
            pos: int,
            value: int
        ) -> None:
            if left == right:
                tree[index] = make_leaf(value)
                return

            mid = (left + right) // 2

            if pos <= mid:
                update(index * 2, left, mid, pos, value)
            else:
                update(index * 2 + 1, mid + 1, right, pos, value)

            tree[index] = merge(
                tree[index * 2],
                tree[index * 2 + 1]
            )

        build(1, 0, n - 1)

        answer = 0

        for pos, value in queries:
            update(1, 0, n - 1, pos, value)

            best = max(
                tree[1].dp[0][0],
                tree[1].dp[0][1],
                tree[1].dp[1][0],
                tree[1].dp[1][1]
            )

            answer = (answer + best) % MOD

        return answer

The implementation begins by defining a segment tree node that stores a 2 x 2 DP matrix. Each entry represents whether the left and right endpoints of the segment are selected.

The make_leaf function initializes a segment containing one element. The empty subsequence contributes 0, while selecting the element contributes max(0, value).

The merge function is the core of the solution. It iterates through all state combinations from the left and right child segments. Invalid adjacency combinations are skipped, and valid combinations are merged into the resulting DP table.

The build function constructs the segment tree recursively.

The update function modifies a single position and recomputes all affected ancestors.

After each query update, the root node contains the DP information for the entire array. The maximum among the four root states is the answer for that query.

Go Solution

package main

import "math"

const MOD int = 1_000_000_007
const NEG_INF int = math.MinInt / 4

type Node struct {
	dp [2][2]int
}

func makeLeaf(value int) Node {
	node := Node{}

	for i := 0; i < 2; i++ {
		for j := 0; j < 2; j++ {
			node.dp[i][j] = NEG_INF
		}
	}

	node.dp[0][0] = 0

	if value > 0 {
		node.dp[1][1] = value
	} else {
		node.dp[1][1] = 0
	}

	return node
}

func merge(left Node, right Node) Node {
	res := Node{}

	for i := 0; i < 2; i++ {
		for j := 0; j < 2; j++ {
			res.dp[i][j] = NEG_INF
		}
	}

	for ls := 0; ls < 2; ls++ {
		for le := 0; le < 2; le++ {
			if left.dp[ls][le] == NEG_INF {
				continue
			}

			for rs := 0; rs < 2; rs++ {
				for re := 0; re < 2; re++ {
					if right.dp[rs][re] == NEG_INF {
						continue
					}

					if le == 1 && rs == 1 {
						continue
					}

					value := left.dp[ls][le] + right.dp[rs][re]

					if value > res.dp[ls][re] {
						res.dp[ls][re] = value
					}
				}
			}
		}
	}

	return res
}

func maximumSumSubsequence(nums []int, queries [][]int) int {
	n := len(nums)

	tree := make([]Node, 4*n)

	var build func(int, int, int)

	build = func(index int, left int, right int) {
		if left == right {
			tree[index] = makeLeaf(nums[left])
			return
		}

		mid := (left + right) / 2

		build(index*2, left, mid)
		build(index*2+1, mid+1, right)

		tree[index] = merge(
			tree[index*2],
			tree[index*2+1],
		)
	}

	var update func(int, int, int, int, int)

	update = func(
		index int,
		left int,
		right int,
		pos int,
		value int,
	) {
		if left == right {
			tree[index] = makeLeaf(value)
			return
		}

		mid := (left + right) / 2

		if pos <= mid {
			update(index*2, left, mid, pos, value)
		} else {
			update(index*2+1, mid+1, right, pos, value)
		}

		tree[index] = merge(
			tree[index*2],
			tree[index*2+1],
		)
	}

	build(1, 0, n-1)

	answer := 0

	for _, query := range queries {
		pos := query[0]
		value := query[1]

		update(1, 0, n-1, pos, value)

		best := NEG_INF

		for i := 0; i < 2; i++ {
			for j := 0; j < 2; j++ {
				if tree[1].dp[i][j] > best {
					best = tree[1].dp[i][j]
				}
			}
		}

		answer = (answer + best) % MOD
	}

	return answer
}

The Go implementation follows the same structure as the Python version, but uses fixed-size arrays for the DP matrix.

Since Go does not have negative infinity for integers, a very small sentinel value is used instead.

The segment tree is stored in a slice of Node structures, and recursive closures are used for both building and updating the tree.

Worked Examples

Example 1

nums = [3,5,9]
queries = [[1,-2],[0,-3]]

Initial Tree

For leaves:

Index	Value	Best
0	3	3
1	5	5
2	9	9

Whole array best:

3 + 9 = 12

This initial value is not added because queries have not started yet.

Query 1

[1, -2]

Updated array:

[3,-2,9]

Possible valid subsequences:

Subsequence	Sum
[]	0
[3]	3
[-2]	-2
[9]	9
[3,9]	12

Maximum:

12

Running total:

12

Query 2

[0, -3]

Updated array:

[-3,-2,9]

Possible valid subsequences:

Subsequence	Sum
[]	0
[-3]	-3
[-2]	-2
[9]	9
[-3,9]	6

Maximum:

9

Running total:

12 + 9 = 21

Final answer:

21

Example 2

nums = [0,-1]
queries = [[0,-5]]

After update:

[-5,-1]

All non-empty subsequences are negative.

Choosing the empty subsequence gives:

0

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(q log n)	Each query performs one segment tree update
Space	O(n)	Segment tree storage

Each segment tree node stores only four DP states, which is constant space per node.

Every update touches O(log n) nodes in the tree. Each merge examines only 16 state combinations, which is constant work.

Therefore the total complexity is:

O(q log n)

which easily fits the problem constraints.

Test Cases

sol = Solution()

# Provided example 1
assert sol.maximumSumSubsequence(
    [3, 5, 9],
    [[1, -2], [0, -3]]
) == 21

# Provided example 2
assert sol.maximumSumSubsequence(
    [0, -1],
    [[0, -5]]
) == 0

# Single positive element
assert sol.maximumSumSubsequence(
    [7],
    [[0, 4]]
) == 4

# Single negative element
assert sol.maximumSumSubsequence(
    [-5],
    [[0, -2]]
) == 0

# All negatives remain negative
assert sol.maximumSumSubsequence(
    [-1, -2, -3],
    [[1, -10], [2, -20]]
) == 0

# Alternating positives
assert sol.maximumSumSubsequence(
    [1, 2, 3, 4],
    [[0, 10]]
) == 13  # choose 10 + 3

# Update creates better non-adjacent structure
assert sol.maximumSumSubsequence(
    [5, 1, 5],
    [[1, 100]]
) == 100

# Multiple updates on same index
assert sol.maximumSumSubsequence(
    [1, 2, 3],
    [[1, 10], [1, -10], [1, 5]]
) == (10 + 4 + 5)

# Zero handling
assert sol.maximumSumSubsequence(
    [0, 0, 0],
    [[1, 0]]
) == 0

# Large values
assert sol.maximumSumSubsequence(
    [100000, -100000, 100000],
    [[1, 50000]]
) == 200000

Test Summary

Test	Why
[3,5,9] with updates	Verifies official example
[0,-1]	Verifies empty subsequence handling
Single positive element	Tests smallest valid array
Single negative element	Ensures answer never becomes negative
All negatives	Verifies repeated zero answers
Alternating positives	Tests standard House Robber behavior
Large middle update	Ensures updates propagate correctly
Repeated updates	Verifies stable tree recomputation
All zeros	Tests neutral values
Large magnitudes	Tests integer handling

Edge Cases

All Elements Are Negative

If every element is negative, the optimal subsequence is the empty subsequence with sum 0.

A common bug is forcing at least one element to be selected. This implementation avoids that by always allowing the s00 state to remain 0.

Single Element Arrays

When n = 1, the left and right endpoints are the same element. Incorrect state initialization can accidentally allow impossible states like selecting only one endpoint.

The implementation correctly initializes only:

s00
s11

for leaf nodes.

Adjacent Boundary Conflicts During Merge

The most subtle issue occurs when merging two segments.

If the right endpoint of the left segment and the left endpoint of the right segment are both selected, then the merged subsequence violates the non-adjacent constraint.

The merge function explicitly rejects this case:

if l_end == 1 and r_start == 1:
    continue

This guarantees that all constructed subsequences remain valid.