Maximum Sum of Non-Adjacent Elements

89.5k
0

A non-empty array nums of positive integers is given. Select a subsequence with no two selected elements at adjacent positions in nums.

Return the maximum possible sum among all valid subsequences.

Example 1

Input: nums = [2, 1, 4, 9]
Output: 11
Explanation: Selecting 2 and 9 produces a valid sum of 11. No other valid selection produces a larger sum.

Example 2

Input: nums = [7]
Output: 7
Explanation: A single element has no adjacent partner, so selecting 7 gives the maximum sum.

Recursion

Each array position offers a small choice: take the value or leave the value. Taking nums[index] blocks nums[index - 1], so the next available prefix ends at index - 2. Skipping nums[index] leaves the prefix ending at index - 1 available.

The state solve(index) stores the best valid sum inside positions 0 through index. The first helper call starts at index n - 1 because the prefix then covers the complete array. Both choices reduce the prefix, so recursion eventually reaches a crossed boundary or a one-element prefix.

Algorithm

  • Begin with solve(index) as the maximum valid sum inside positions 0 through index, so every recursive call carries one clear prefix meaning.

  • Return 0 after index crosses the left boundary because no array value remains available for selection.

  • Return nums[0] at index 0 because a one-element positive prefix has only one best selection.

  • Take nums[index] together with solve(index - 2) because selecting the current value makes the adjacent previous position unavailable.

  • Skip nums[index] through solve(index - 1) because the previous prefix then remains completely available.

  • Compare the take and skip sums so the larger valid choice becomes the answer for the current prefix.

  • Start recursion from n - 1 because the final prefix represents every position in the input array.

Dry Run

Maximum Sum of Non Adjacent Element Recursion

Maximum Sum of Non Adjacent Element Recursion

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the best sum through a chosen index.
int solve(int index, vector<int>& nums) {
// A crossed boundary contributes no selected value.
if (index < 0) {
return 0;
}
// A one-value prefix has one best selection.
if (index == 0) {
return nums[0];
}
// Taking the value forces one adjacent skip.
int take = nums[index] + solve(index - 2, nums);
// Skipping the value keeps the previous prefix.
int skip = solve(index - 1, nums);
// The larger valid choice gives the prefix answer.
return max(take, skip);
}
public:
// Returns the maximum valid non-adjacent sum.
int maximumNonAdjacentSum(vector<int>& nums) {
int n = nums.size();
// The final index represents the complete array.
return solve(n - 1, nums);
}
};
// Driver code
int main() {
vector<int> nums = {2, 1, 4, 9};
Solution obj;
cout << obj.maximumNonAdjacentSum(nums);
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(2N), where N is the number of indices, because each index can create two recursive choices: take or skip.

Space Complexity: O(N), because the recursion depth can grow to at most N calls and no additional growing data structure is used.

Memoization

Direct recursion reaches the same prefix through different decision paths. For example, solve(1) can appear below both solve(3) and solve(2). Recalculating an already solved prefix adds work without adding new information.

Memoization keeps the recursive take-or-skip idea unchanged and adds an array named dp. A saved dp[index] value answers every later request for the same prefix immediately, reducing the recursion tree to one calculation per index.

Algorithm

  • Keep solve(index) as the best valid sum through index so the recursive state remains identical to direct recursion.

  • Create a dp array filled with -1 because every valid answer is positive and the sentinel clearly marks an unfinished state.

  • Return the boundary answers before a cache lookup because crossed and one-element prefixes need no stored calculation.

  • Reuse dp[index] after a cache hit so repeated paths avoid rebuilding the same recursive subtree.

  • Take nums[index] with solve(index - 2) because selecting the current value rules out the adjacent previous position.

  • Skip nums[index] with solve(index - 1) because leaving the current value preserves the entire previous prefix.

  • Store the larger branch in dp[index] so every future request receives the finished prefix answer in constant time.

  • Start with solve(n - 1) because the last prefix contains the complete input array.

Dry Run

maximum-sum-of-non-adjacent-elements-memoization-dp-minus-one.png

maximum-sum-of-non-adjacent-elements-memoization-dp-minus-one.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the cached best sum through an index.
int solve(int index, vector<int>& nums, vector<int>& dp) {
// A crossed boundary contributes no selected value.
if (index < 0) {
return 0;
}
// A one-value prefix has one best selection.
if (index == 0) {
return nums[0];
}
// A saved answer avoids rebuilding a subtree.
if (dp[index] != -1) {
return dp[index];
}
// Taking the value forces one adjacent skip.
int take = nums[index] + solve(index - 2, nums, dp);
// Skipping the value keeps the previous prefix.
int skip = solve(index - 1, nums, dp);
// Saving the larger choice supports later reuse.
dp[index] = max(take, skip);
return dp[index];
}
public:
// Returns the maximum valid non-adjacent sum.
int maximumNonAdjacentSum(vector<int>& nums) {
int n = nums.size();
// Negative entries mark unfinished prefix states.
vector<int> dp(n, -1);
// The final index represents the complete array.
return solve(n - 1, nums, dp);
}
};
// Driver code
int main() {
vector<int> nums = {2, 1, 4, 9};
Solution obj;
cout << obj.maximumNonAdjacentSum(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of prefix states, because each state is computed once and reused through memoization.

Space Complexity: O(N), because the dp array stores N values and the recursion stack can contain at most N calls.

Tabulation

Memoization proves every state depends only on smaller prefix states. Tabulation fills the same answers from left to right, so each required value already exists before a later prefix is processed.

The meaning stays unchanged: dp[index] stores the best valid sum through index. The first two prefix answers provide a stable starting point, and a loop replaces recursive calls with direct table lookups.

Algorithm

  • Create an array named dp with one entry per input position so every prefix answer has a dedicated location.

  • Store nums[0] in dp[0] because a one-element positive prefix has one best selection.

  • Return dp[0] for an array of length one because no larger prefix needs construction.

  • Store max(nums[0], nums[1]) in dp[1] because adjacent positions cannot both contribute to the second prefix.

  • Move from index 2 toward the final position so both required earlier answers exist before each transition.

  • Add nums[index] to dp[index - 2] for the take sum, preserving the required gap from the current position.

  • Compare the take sum with dp[index - 1] for the skip sum, then store the larger result so dp[index] preserves the best prefix answer.

  • Return dp[n - 1] because the final table entry represents the complete array.

Dry Run

Maximum Sum of Non Adjacent Element Tabulation

Maximum Sum of Non Adjacent Element Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum valid non-adjacent sum.
int maximumNonAdjacentSum(vector<int>& nums) {
int n = nums.size();
// Each entry stores one finished prefix answer.
vector<int> dp(n, 0);
dp[0] = nums[0];
// A one-value array already has a final answer.
if (n == 1) {
return dp[0];
}
// Adjacent first values cannot both be selected.
dp[1] = max(nums[0], nums[1]);
// Later states need two finished earlier states.
for (int index = 2; index < n; index++) {
// Taking the value uses the two-back answer.
int take = nums[index] + dp[index - 2];
// Skipping the value keeps the prior answer.
int skip = dp[index - 1];
// The larger valid choice completes the state.
dp[index] = max(take, skip);
}
// The last state covers the complete input array.
return dp[n - 1];
}
};
// Driver code
int main() {
vector<int> nums = {2, 1, 4, 9};
Solution obj;
cout << obj.maximumNonAdjacentSum(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of input positions, because each prefix state is computed once with constant work.

Space Complexity: O(N), because the dp array stores one value for each input position, while the iterative approach uses no recursion stack.

Space Optimization

Tabulation reveals a small memory pattern: the current prefix answer needs only the previous prefix answer and the answer from two positions earlier. Older table entries never appear in a later transition.

The variable previous represents dp[index - 1], while secondPrevious represents dp[index - 2]. First, current combines the take and skip choices. Next, shifting secondPrevious before previous preserves both old values in the required order for the following index.

Algorithm

  • Store nums[0] in previous because the first prefix answer equals the only available positive value.

  • Store 0 in secondPrevious because the imaginary prefix before index 0 contributes no selected value.

  • Move from index 1 toward the end so each current answer can use the two retained earlier states.

  • Add nums[index] to secondPrevious for the take sum because the two-back prefix respects the non-adjacent rule.

  • Keep previous as the skip sum because ignoring the current value preserves the best earlier prefix.

  • Set current to the larger sum so the new prefix receives the best valid choice.

  • Shift secondPrevious to the old previous, then shift previous to current, preserving both required states for the next index.

  • Return previous after the loop because the variable then represents the final prefix answer.

Dry Run

Maximum Sum of Non Adjacent Element Space Optimization

Maximum Sum of Non Adjacent Element Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum valid non-adjacent sum.
int maximumNonAdjacentSum(vector<int>& nums) {
int n = nums.size();
int secondPrevious = 0;
int previous = nums[0];
// Each step needs only two earlier answers.
for (int index = 1; index < n; index++) {
// Taking the value uses the two-back answer.
int take = nums[index] + secondPrevious;
// Skipping the value keeps the prior answer.
int skip = previous;
// Current keeps the larger valid choice.
int current = max(take, skip);
// Ordered shifts preserve both needed states.
secondPrevious = previous;
previous = current;
}
// Previous now represents the complete array.
return previous;
}
};
// Driver code
int main() {
vector<int> nums = {2, 1, 4, 9};
Solution obj;
cout << obj.maximumNonAdjacentSum(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N), where N is the number of input positions, because each position is processed once with constant work.

Space Complexity: O(1), because only a fixed number of variables are used and no dp array or recursion stack is required.

Interview follow-up Questions

Yes. House Robber adds a story around the same linear array rule. Both problems use an identical take-or-skip dynamic programming transition.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Given an array arr containing n positive integers and a non-negative integer target , select each array position at most once. Return true if the sum of selected elements equals targe...

55.1k
Comments0