Choose a subsequence whose elements alternately add and subtract to maximize the total.
Given an integer array, select any subsequence (possibly empty) and assign its elements alternating signs starting with plus on the first chosen element: +, -, +, -, ...
Your goal is to maximize the resulting alternating sum. The subsequence does not need to be contiguous, but the order of chosen elements must follow the original array order.
Return the maximum alternating subsequence sum achievable.
Input Format
- An integer array
nums. nums[i]is the value at positioni.- You may choose any subsequence, including the empty subsequence.
Output Format
- Return a single integer: the maximum alternating subsequence sum.
Constraints
1 <= nums.length <= 1e50 <= nums[i] <= 1e5- The answer fits in a 64-bit signed integer.
Example 1
Input
nums = [4, 2, 5, 3]
Output
7
Explanation
One optimal subsequence is [4, 2, 5]. Its alternating sum is 4 - 2 + 5 = 7.
Example 2
Input
nums = [5, 6, 7, 8]
Output
8
Explanation
Take the subsequence [8]. The alternating sum is 8, which is maximal.
Show 1 more example
Example 3
Input
nums = [6, 2, 1, 2, 4, 5]
Output
10
Explanation
One optimal subsequence is [6, 2, 4, 5]. Its alternating sum is 6 - 2 + 4 - 5 = 3, so that is not optimal. A better choice is [6, 1, 4, 5] giving 6 - 1 + 4 - 5 = 4, and the maximum achievable value is 10.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.