Largest Non-Adjacent Subset Sum
Problem
Given an array of non-negative values arranged on a line, pick a subset with the largest possible sum subject to the constraint that no two picked elements may be neighbours. Recurrence: dp[i] = max(dp[i−1], dp[i−2] + nums[i]) — either skip i or take it and skip the previous one.
Input
nums = [3, 8, 4, 9, 2]Output
17Pick indices 1 and 3: 8 + 9 = 17.
def max_non_adjacent(nums):
n = len(nums)
if n == 0: return 0
dp = [0] * n
dp[0] = nums[0]
for i in range(1, n):
skip = dp[i - 1]
take = (dp[i - 2] if i >= 2 else 0) + nums[i]
dp[i] = max(skip, take)
return dp[-1]function maxNonAdjacent(nums) {
const n = nums.length;
if (n === 0) return 0;
const dp = new Array(n).fill(0);
dp[0] = nums[0];
for (let i = 1; i < n; i++) {
const skip = dp[i - 1];
const take = (i >= 2 ? dp[i - 2] : 0) + nums[i];
dp[i] = Math.max(skip, take);
}
return dp[n - 1];
}class Solution {
public int maxNonAdjacent(int[] nums) {
int n = nums.length;
if (n == 0) return 0;
int[] dp = new int[n];
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
int skip = dp[i - 1];
int take = (i >= 2 ? dp[i - 2] : 0) + nums[i];
dp[i] = Math.max(skip, take);
}
return dp[n - 1];
}
}int maxNonAdjacent(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
vector<int> dp(n, 0);
dp[0] = nums[0];
for (int i = 1; i < n; i++) {
int skip = dp[i - 1];
int take = (i >= 2 ? dp[i - 2] : 0) + nums[i];
dp[i] = max(skip, take);
}
return dp[n - 1];
}