Loading problem...
You are given an array of non-negative integers representing values associated with a sequence of elements arranged in a line. Your goal is to select a subset of these elements such that the total value is maximized, with one critical restriction: you cannot select two elements that are directly adjacent to each other in the array.
In other words, if you select the element at index i, you cannot select the elements at indices i-1 or i+1. Design an algorithm to determine the maximum sum you can achieve by choosing non-adjacent elements.
This problem models scenarios where selecting consecutive items incurs a penalty or is prohibited—such as scheduling tasks that require buffer time between them, or selecting resources with mandatory cooling periods.
nums = [1,2,3,1]4Select elements at index 0 (value = 1) and index 2 (value = 3). Total sum = 1 + 3 = 4. Selecting index 1 and index 3 would give 2 + 1 = 3, which is less optimal.
nums = [2,7,9,3,1]12Select elements at index 0 (value = 2), index 2 (value = 9), and index 4 (value = 1). Total sum = 2 + 9 + 1 = 12. This is optimal because indices 0, 2, and 4 are non-adjacent.
nums = [1,2]2With only two adjacent elements, select the larger one. Element at index 1 (value = 2) is the optimal choice.
Constraints