Maximize sum with no adjacent elements

Given an array of non-negative integers nums, choose a subset of elements such that no two chosen elements are adjacent in the original array.

Return the maximum possible sum of the chosen elements.

Input

• nums: array of integers, 0 <= nums[i]

Output

• An integer: the maximum sum achievable without choosing adjacent elements.

Constraints (typical interview constraints)

• 1 <= n <= 10^5
• 0 <= nums[i] <= 10^9

Examples

• nums = [1,2,3,1] → 4 (choose 1 and 3)
• nums = [2,7,9,3,1] → 12 (choose 2, 9, 1)

Maximize sum with no adjacent elements

Hints

1. This is the classic 'House Robber' problem. At each index, you either skip the current element or take it (which forbids taking the previous one).
2. Track two running values: the best sum that INCLUDES the current element and the best sum that EXCLUDES it. The included value can only build on the previous excluded value.
3. You only need the two values from the previous step, so O(1) extra space suffices. Final answer is max(include, exclude).