Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
You are given a 0-indexed integer array nums.
A subsequence of nums having length k and consisting of indices i0 < i1 < ... < ik-1 is balanced if the following holds:
nums[ij] - nums[ij-1] >= ij - ij-1, for every j in the range [1, k - 1].A subsequence of nums having length 1 is considered balanced.
Return an integer denoting the maximum possible sum of elements in a balanced subsequence of nums.
A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.
Example 1:
Input: nums = [3,3,5,6] Output: 14 Explanation: In this example, the subsequence [3,5,6] consisting of indices 0, 2, and 3 can be selected. nums[2] - nums[0] >= 2 - 0. nums[3] - nums[2] >= 3 - 2. Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums. The subsequence consisting of indices 1, 2, and 3 is also valid. It can be shown that it is not possible to get a balanced subsequence with a sum greater than 14.
Example 2:
Input: nums = [5,-1,-3,8] Output: 13 Explanation: In this example, the subsequence [5,8] consisting of indices 0 and 3 can be selected. nums[3] - nums[0] >= 3 - 0. Hence, it is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums. It can be shown that it is not possible to get a balanced subsequence with a sum greater than 13.
Example 3:
Input: nums = [-2,-1] Output: -1 Explanation: In this example, the subsequence [-1] can be selected. It is a balanced subsequence, and its sum is the maximum among the balanced subsequences of nums.
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 109Problem summary: You are given a 0-indexed integer array nums. A subsequence of nums having length k and consisting of indices i0 < i1 < ... < ik-1 is balanced if the following holds: nums[ij] - nums[ij-1] >= ij - ij-1, for every j in the range [1, k - 1]. A subsequence of nums having length 1 is considered balanced. Return an integer denoting the maximum possible sum of elements in a balanced subsequence of nums. A subsequence of an array is a new non-empty array that is formed from the original array by deleting some (possibly none) of the elements without disturbing the relative positions of the remaining elements.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Binary Search · Dynamic Programming · Segment Tree
[3,3,5,6]
[5,-1,-3,8]
[-2,-1]
number-of-pairs-satisfying-inequality)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2926: Maximum Balanced Subsequence Sum
class BinaryIndexedTree {
private int n;
private long[] c;
private final long inf = 1L << 60;
public BinaryIndexedTree(int n) {
this.n = n;
c = new long[n + 1];
Arrays.fill(c, -inf);
}
public void update(int x, long v) {
while (x <= n) {
c[x] = Math.max(c[x], v);
x += x & -x;
}
}
public long query(int x) {
long mx = -inf;
while (x > 0) {
mx = Math.max(mx, c[x]);
x -= x & -x;
}
return mx;
}
}
class Solution {
public long maxBalancedSubsequenceSum(int[] nums) {
int n = nums.length;
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = nums[i] - i;
}
Arrays.sort(arr);
int m = 0;
for (int i = 0; i < n; ++i) {
if (i == 0 || arr[i] != arr[i - 1]) {
arr[m++] = arr[i];
}
}
BinaryIndexedTree tree = new BinaryIndexedTree(m);
for (int i = 0; i < n; ++i) {
int j = search(arr, nums[i] - i, m) + 1;
long v = Math.max(tree.query(j), 0) + nums[i];
tree.update(j, v);
}
return tree.query(m);
}
private int search(int[] nums, int x, int r) {
int l = 0;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}
// Accepted solution for LeetCode #2926: Maximum Balanced Subsequence Sum
const inf int = 1e18
type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) BinaryIndexedTree {
c := make([]int, n+1)
for i := range c {
c[i] = -inf
}
return BinaryIndexedTree{n: n, c: c}
}
func (bit *BinaryIndexedTree) update(x, v int) {
for x <= bit.n {
bit.c[x] = max(bit.c[x], v)
x += x & -x
}
}
func (bit *BinaryIndexedTree) query(x int) int {
mx := -inf
for x > 0 {
mx = max(mx, bit.c[x])
x -= x & -x
}
return mx
}
func maxBalancedSubsequenceSum(nums []int) int64 {
n := len(nums)
arr := make([]int, n)
for i, x := range nums {
arr[i] = x - i
}
sort.Ints(arr)
m := 0
for i, x := range arr {
if i == 0 || x != arr[i-1] {
arr[m] = x
m++
}
}
arr = arr[:m]
tree := NewBinaryIndexedTree(m)
for i, x := range nums {
j := sort.SearchInts(arr, x-i) + 1
v := max(tree.query(j), 0) + x
tree.update(j, v)
}
return int64(tree.query(m))
}
# Accepted solution for LeetCode #2926: Maximum Balanced Subsequence Sum
class BinaryIndexedTree:
def __init__(self, n: int):
self.n = n
self.c = [-inf] * (n + 1)
def update(self, x: int, v: int):
while x <= self.n:
self.c[x] = max(self.c[x], v)
x += x & -x
def query(self, x: int) -> int:
mx = -inf
while x:
mx = max(mx, self.c[x])
x -= x & -x
return mx
class Solution:
def maxBalancedSubsequenceSum(self, nums: List[int]) -> int:
arr = [x - i for i, x in enumerate(nums)]
s = sorted(set(arr))
tree = BinaryIndexedTree(len(s))
for i, x in enumerate(nums):
j = bisect_left(s, x - i) + 1
v = max(tree.query(j), 0) + x
tree.update(j, v)
return tree.query(len(s))
// Accepted solution for LeetCode #2926: Maximum Balanced Subsequence Sum
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #2926: Maximum Balanced Subsequence Sum
// class BinaryIndexedTree {
// private int n;
// private long[] c;
// private final long inf = 1L << 60;
//
// public BinaryIndexedTree(int n) {
// this.n = n;
// c = new long[n + 1];
// Arrays.fill(c, -inf);
// }
//
// public void update(int x, long v) {
// while (x <= n) {
// c[x] = Math.max(c[x], v);
// x += x & -x;
// }
// }
//
// public long query(int x) {
// long mx = -inf;
// while (x > 0) {
// mx = Math.max(mx, c[x]);
// x -= x & -x;
// }
// return mx;
// }
// }
//
// class Solution {
// public long maxBalancedSubsequenceSum(int[] nums) {
// int n = nums.length;
// int[] arr = new int[n];
// for (int i = 0; i < n; ++i) {
// arr[i] = nums[i] - i;
// }
// Arrays.sort(arr);
// int m = 0;
// for (int i = 0; i < n; ++i) {
// if (i == 0 || arr[i] != arr[i - 1]) {
// arr[m++] = arr[i];
// }
// }
// BinaryIndexedTree tree = new BinaryIndexedTree(m);
// for (int i = 0; i < n; ++i) {
// int j = search(arr, nums[i] - i, m) + 1;
// long v = Math.max(tree.query(j), 0) + nums[i];
// tree.update(j, v);
// }
// return tree.query(m);
// }
//
// private int search(int[] nums, int x, int r) {
// int l = 0;
// while (l < r) {
// int mid = (l + r) >> 1;
// if (nums[mid] >= x) {
// r = mid;
// } else {
// l = mid + 1;
// }
// }
// return l;
// }
// }
// Accepted solution for LeetCode #2926: Maximum Balanced Subsequence Sum
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(-Infinity);
}
update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] = Math.max(this.c[x], v);
x += x & -x;
}
}
query(x: number): number {
let mx = -Infinity;
while (x > 0) {
mx = Math.max(mx, this.c[x]);
x -= x & -x;
}
return mx;
}
}
function maxBalancedSubsequenceSum(nums: number[]): number {
const n = nums.length;
const arr = Array(n).fill(0);
for (let i = 0; i < n; ++i) {
arr[i] = nums[i] - i;
}
arr.sort((a, b) => a - b);
let m = 0;
for (let i = 0; i < n; ++i) {
if (i === 0 || arr[i] !== arr[i - 1]) {
arr[m++] = arr[i];
}
}
arr.length = m;
const tree = new BinaryIndexedTree(m);
const search = (nums: number[], x: number): number => {
let [l, r] = [0, nums.length];
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (let i = 0; i < n; ++i) {
const j = search(arr, nums[i] - i) + 1;
const v = Math.max(tree.query(j), 0) + nums[i];
tree.update(j, v);
}
return tree.query(m);
}
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.