aloalgoLargest Sum of Non-Adjacent Numbers
Hard
You are given a list of integers, find the largest sum of a subsequence of non-adjacent numbers. The numbers in the list can be positive, negative, or zero.
If all numbers are negative, the largest sum is 0 (by choosing an empty subsequence).
Example 1
Input
[2, 4, 6, 2, 5]
Output
13
Explanation:
The optimal sum is achieved by picking 2, 6, and 5 (2 + 6 + 5 = 13).
Example 2
Input
[5, 1, 1, 5]
Output
10
Explanation:
The optimal sum is achieved by picking 5 and 5 (5 + 5 = 10).
Example 3
Input
[5, 5, 10, 100, 10, 5]
Output
110
Explanation:
The optimal sum is achieved by picking 5, 100, and 5 (5 + 100 + 5 = 110).
Input
[2, 4, 6, 2, 5]
Output
13