Maximize sum of non-adjacent values

Q: Maximize sum of non-adjacent values

This question evaluates algorithmic problem-solving skills, specifically understanding of dynamic programming and optimization when selecting non-adjacent elements, within the Coding & Algorithms domain.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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)