1132. Maximum Alternating Subsequence Sum

Given an array nums, the alternating sum of a subsequence is the sum of its elements at even indices minus the sum at odd indices (0-indexed within the subsequence). Return the maximum alternating sum over all subsequences. The input is JSON {nums}.

Input: JSON {nums}.

Output: Integer — the maximum alternating subsequence sum.

Examples

Input: {"nums":[4,2,5,3]}
Output: 7
Explanation: Subsequence [4,2,5] gives 4-2+5=7.

Input: {"nums":[6,2,1,2,4,5]}
Output: 10
Explanation: An optimal subsequence sums to 10.

Input: {"nums":[5]}
Output: 5
Explanation: A single element.

Constraints

• 1<=n<=10^5
• 1<=nums[i]<=10^5

Asked by