Practice/Amazon/Leetcode 198. House Robber

Leetcode 198. House Robber

CodingMust

Problem

You are given an array of non-negative integers where each element represents a value. Your task is to find the maximum sum you can obtain by selecting elements from the array, with the constraint that no two selected elements can be adjacent to each other in the array.

For example, if you select the element at index i, you cannot select the elements at indices i-1 or i+1.

Requirements

1. Return the maximum possible sum that can be obtained
2. Handle arrays of any length (including edge cases with 1 or 2 elements)
3. No two selected elements should be adjacent in the original array
4. All elements in the input array are non-negative integers

Constraints

• 1 ≤ nums.length ≤ 1000
• 0 ≤ nums[i] ≤ 10000
• Expected time complexity: O(n)
• Expected space complexity: O(1) for optimal solution

Examples

Example 1:

Input: nums = [2, 7, 9, 3, 1] Output: 12 Explanation: Select elements at indices 0, 2, and 4 (values 2, 9, 1). Sum = 2 + 9 + 1 = 12

Example 2:

Input: nums = [5, 1] Output: 5 Explanation: Select the first element (5) for maximum sum

Example 3:

Input: nums = [5, 3, 4, 11, 2] Output: 16 Explanation: Select elements at indices 0 and 3 (values 5 and 11). Sum = 5 + 11 = 16