Maximize sum of non-adjacent values

Problem

You are given an integer array nums representing the amount of money available at each house along a street.

If you take money from house i, you cannot take money from house i-1 or i+1 (no two selected houses may be adjacent).

Return the maximum amount of money you can take.

Input

• nums: an array of integers (typically non-negative)

Output

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

Constraints

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

Examples

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