BudiBadu Logo

Max Non-Adjacent Sum

Array Easy 3 views
Like20

In Max Non-Adjacent Sum, you’re given a sequence of non-negative integers. Your mission is to collect the largest possible sum with one strict rule: you may Not select two values that sit next to each other in the sequence. Each choice to take a value automatically blocks its immediate neighbors from being picked!

The "secret sauce" here is Iterative Choice (DP). At each step i, you decide: "Is it better to take this value plus the best sum from i-2, or just stick with the best sum from i-1?" By making this comparison as you walk the list, you find the global maximum without ever checking every combination. This approach is lightning fast (O(N)) and solves the problem in a single pass. Mastering this "pick or skip" logic is a fundamental building block for optimization and resource allocation tasks in any professional software environment. Return the highest total obtainable as a single integer!

Because this is a counting/optimization-style challenge, dynamic programming is usually the safest approach: define what each index or state means, initialize valid base states, and make transitions explicit. If the problem uses modulo arithmetic, apply modulo at every accumulation step so large intermediate totals never corrupt the final answer.

Examples

Example 1
Input
nums = [1, 2, 3, 1]
Output
4
Explanation

Choose 1 (index 0) and 3 (index 2) for a total of 4.

Example 2
Input
nums = [2, 7, 9, 3, 1]
Output
12
Explanation

One optimal choice is 2 (index 0), 9 (index 2), and 1 (index 4) for a total of 12.

Example 3
Input
nums = [5, 1, 1, 5]
Output
10
Explanation

Choose 5 (index 0) and 5 (index 3) for a total of 10.

Algorithm Flow

Recommendation Algorithm Flow for Max Non-Adjacent Sum - Budibadu
Recommendation Algorithm Flow for Max Non-Adjacent Sum - Budibadu

Best Answers

java
class Solution {
    public int rob(Object nums) {
        int[] arr = (int[]) nums;
        if (arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return arr[0];
        }
        int prev2 = arr[0];
        int prev1 = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            int curr = Math.max(prev1, prev2 + arr[i]);
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}