Maximize sum without choosing adjacent elements

Q: Maximize sum without choosing adjacent elements

This question evaluates a candidate's understanding of array-based optimization and dynamic programming concepts for computing a maximum sum under non-adjacent selection constraints.

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

Loading...

Problem

You are given an integer array nums where nums[i] is the value in position i.

Select a subset of indices such that no two selected indices are adjacent (i.e., you cannot select both i and i+1). Return the maximum possible sum of the selected values.

Input

nums : array of integers (can include 0 )

Output

An integer: the maximum achievable sum under the non-adjacent constraint.

Constraints (reasonable interview assumptions)

1 <= nums.length <= 2 * 10^5
0 <= nums[i] <= 10^9
Time target: O(n)
Space target: O(1) or O(n)

Examples

nums = [2, 7, 9, 3, 1] → 12 (pick 2 + 9 + 1 )
nums = [1, 2, 3, 1] → 4 (pick 1 + 3 )