Maximize sum of non-adjacent values
Company: Samsung
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## 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)
Quick Answer: This question evaluates algorithmic problem-solving skills, specifically understanding of dynamic programming and optimization when selecting non-adjacent elements, within the Coding & Algorithms domain.
Return the maximum sum from nums with no two selected positions adjacent.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,2,3,1],)
Expected Output: 4
Explanation: Prompt example 1.
Input: ([2,7,9,3,1],)
Expected Output: 12
Explanation: Prompt example 2.
Input: ([],)
Expected Output: 0
Explanation: No houses.
Hints
- Choose a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.