Resilient Path Weight — Problem Statement & Solution Guide
Problem Description
You are given an array of integers weights representing the signal strength of sensors arranged in a linear chain. Your task is to compute the maximum possible sum of signal strengths by selecting a subset of sensors such that no two selected sensors are adjacent in the original sequence. This selection constraint ensures that the data path remains stable even if a single node fails, as no critical dependency exists between consecutive nodes.
The function should return the maximum sum achievable under this non-adjacency constraint. If the array is empty, return 0. If the array contains only one element, return that element's value. The solution must efficiently handle large input sizes, implying a dynamic programming or optimized recursive approach is required rather than brute-force enumeration of all subsets.
Input: An array weights of integers.
Output: An integer representing the maximum sum of non-adjacent elements.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Resilient Path Weight"
WHY DOES IT MATTER?
The non‑adjacent selection pattern appears in resource allocation, scheduling, and financial portfolio problems where adjacent choices conflict. Mastering this DP pattern equips engineers to convert exponential brute‑force reasoning into linear solutions, a core skill for high‑performance code.
OPTIMIZATION CHALLENGE
The key insight is that the optimal substructure only needs the two previous results, allowing us to collapse the DP table into two scalar variables (prev and prevPrev). This reduces both time and space to O(n) and O(1) respectively.
REAL-WORLD CONNECTION
Imagine a distributed sensor network where activating two neighboring nodes causes interference. The optimal activation plan mirrors the DP: decide for each node whether to power it on (and skip its neighbor) or keep it off, maximizing total signal strength while preserving network stability.
During an interview, write the recurrence first, then immediately show the space‑optimized version. It demonstrates both algorithmic understanding and practical coding efficiency.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem is a classic instance of the maximum‑sum‑non‑adjacent subsequence, often solved via dynamic programming. The naive solution enumerates every subset of indices, leading to exponential time because each element has two choices (pick or skip) and the adjacency constraint forces a combinatorial explosion. By recognizing that the optimal solution for the first i elements depends only on the optimal solutions for the first i‑1 and i‑2 elements, we can formulate a recurrence: dp[i] = max(dp[i-1], dp[i-2] + weights[i]). This recurrence captures the decision to either exclude the current sensor (inherit the best sum up to i‑1) or include it (add its weight to the best sum up to i‑2). The optimal paradigm is thus a linear‑time, bottom‑up DP or a space‑optimized rolling‑variable version, both of which avoid redundant recomputation and scale to large inputs.
Interview Questions on This Problem
Q1How would you modify the solution if the sensors were arranged in a circle, i.e., the first and last sensors are also adjacent?
Treat the circular case as two linear sub‑problems: one excluding the first sensor and one excluding the last sensor. Compute the maximum non‑adjacent sum for each sub‑array using the standard DP and return the larger of the two results.
Q2Can you extend the algorithm to handle a constraint where you cannot pick more than two consecutive sensors?
Introduce a DP state with three dimensions: dp[i][k] where k = 0,1,2 indicates how many of the last consecutive sensors have been selected. Transition accordingly, ensuring k never exceeds 2, yielding O(n) time and O(1) space with rolling variables.
Q3What is the time‑space trade‑off when you need to reconstruct the actual set of selected sensors, not just the maximum sum?
To reconstruct, store a predecessor or boolean choice array during the DP pass, which increases space to O(n). Alternatively, you can recompute decisions in a second pass using only the DP values, keeping space O(1) but at the cost of an extra O(n) traversal.
Examples
Input
weights = [3, 2, 7, 10]
Output
13
Explanation: We evaluate two main strategies: either include the first element (3) or exclude it. If we include 3, we cannot include 2, so we look at the subarray [7, 10]. The best from [7, 10] is 10 (since 10 > 7). Total = 3 + 10 = 13. If we exclude 3, we look at [2, 7, 10]. The best from [2, 7, 10] is 12 (2 + 10). Since 13 > 12, the maximum sum is 13. The selected indices are 0 and 3.
Input
weights = [5, 1, 1, 5]
Output
10
Explanation: Option 1: Select index 0 (5) and index 3 (5). Sum = 10. Option 2: Select index 1 (1) and index 3 (5). Sum = 6. Option 3: Select index 0 (5) and index 2 (1). Sum = 6. Option 4: Select index 1 (1) and index 2 (1). Sum = 2. The maximum is 10, achieved by selecting the first and last elements.
Input
weights = [1, 2, 3, 4, 5]
Output
9
Explanation: We can select indices 0, 2, and 4: 1 + 3 + 5 = 9. Alternatively, selecting indices 1 and 3 gives 2 + 4 = 6. Selecting indices 0 and 3 gives 1 + 4 = 5. Selecting indices 1 and 4 gives 2 + 5 = 7. The maximum sum is 9.
Input
weights = [-1, -2, -3]
Output
-1
Explanation: Since all values are negative, we must select the least negative value to maximize the sum. We can select index 0 (-1), index 1 (-2), or index 2 (-3). The maximum value is -1. Note that we cannot select multiple elements if they are adjacent, but even if we could, adding negative numbers would decrease the sum. Thus, the optimal choice is the single largest element, which is -1.
Constraints
- 1 <= weights.length <= 10^5
- -10^9 <= weights[i] <= 10^9
- The answer is guaranteed to fit in a 64-bit integer.
Optimal Approach & Strategy
Use dynamic programming with the recurrence dp[i] = max(dp[i-1], dp[i-2] + weights[i]), iterating once and keeping only two previous values for O(n) time and O(1) space.
Brute Force Approach
Enumerate every subset of sensors, checking the adjacency rule and tracking the maximum sum; this runs in O(2^n) time.
Verified Code Solutions
/**
* @param {number[]} weights
* @return {number}
*/
var resilientPathWeight = function(weights) {
const n = weights.length;
if (n === 0) return 0;
if (n === 1) return weights[0];
const dp = new Array(n).fill(0);
dp[0] = weights[0];
dp[1] = Math.max(weights[0], weights[1]);
for (let i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + weights[i]);
}
return dp[n - 1];
};class Solution {
public:
int resilientPathWeight(vector<int>& weights) {
int n = weights.size();
if (n == 0) return 0;
if (n == 1) return weights[0];
vector<int> dp(n, 0);
dp[0] = weights[0];
dp[1] = max(weights[0], weights[1]);
for (int i = 2; i < n; ++i) {
dp[i] = max(dp[i - 1], dp[i - 2] + weights[i]);
}
return dp[n - 1];
}
};class Solution {
public int resilientPathWeight(int[] weights) {
int n = weights.length;
if (n == 0) return 0;
if (n == 1) return weights[0];
int[] dp = new int[n];
dp[0] = weights[0];
dp[1] = Math.max(weights[0], weights[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + weights[i]);
}
return dp[n - 1];
}
}class Solution:
def resilientPathWeight(self, weights: List[int]) -> int:
n = len(weights)
if n == 0:
return 0
if n == 1:
return weights[0]
dp = [0] * n
dp[0] = weights[0]
dp[1] = max(weights[0], weights[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + weights[i])
return dp[n - 1]/**
* @param {number[]} weights
* @return {number}
*/
var resilientPathWeight = function(weights) {
const n = weights.length;
if (n === 0) return 0;
if (n === 1) return weights[0];
const dp = new Array(n).fill(0);
dp[0] = weights[0];
dp[1] = Math.max(weights[0], weights[1]);
for (let i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + weights[i]);
}
return dp[n - 1];
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.