Maximize sum with no adjacent elements

Q: Maximize sum with no adjacent elements

This question evaluates understanding of dynamic programming and array-based optimization, assessing competency in designing algorithms that maximize a sum under adjacency 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

Given an array of non-negative integers nums, choose a subset of elements such that no two chosen elements are adjacent in the original array.

Return the maximum possible sum of the chosen elements.

Input

nums : array of integers, 0 <= nums[i]

Output

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

Constraints (typical interview constraints)

1 <= n <= 10^5
0 <= nums[i] <= 10^9

Examples

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

Maximize sum with no adjacent elements

Quick Overview

Input

Output

Constraints (typical interview constraints)

Examples

Comments (0)