Maximum Non-Adjacent Sum

You are given an integer array nums. Choose a subset of its elements so that no two chosen elements are adjacent in the array (their indices never differ by exactly 1). Return the maximum possible sum of the chosen elements.

The subset may be empty, and the sum of an empty subset is 0. Since every value satisfies nums[i] $\geq 0$, the answer is never negative.

Examples

Example 1

Input: nums = [1,2,3,1]
Output: 4
Explanation: Take indices 0 and 2 (values 1 and 3), which are not adjacent.
Sum = 1 + 3 = 4.

Example 2

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Take indices 0, 2, and 4 (values 2, 9, and 1), no two of which are adjacent.
Sum = 2 + 9 + 1 = 12.