Best Alternating Sum of an Ordered Selection
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Choose a subsequence from the positive integers in `nums` while preserving their original order. Reindex the selected entries from zero, add those at even selected positions and subtract those at odd selected positions. Return the maximum possible alternating sum.
```cpp
class Solution {
public:
long long maxAlternatingSum(vector<int>& nums);
};
```
### Examples
**Example 1:**
```text
nums = [7,3,8,2]
Output: 12
Explanation: Selecting [7,3,8] gives 7-3+8 = 12.
```
**Example 2:**
```text
nums = [2,4,6]
Output: 6
Explanation: The single entry [6] is optimal; adding an earlier positive-negative pair cannot improve it.
```
### Constraints
- `1 <= nums.length <= 10^5`.
- `1 <= nums[i] <= 10^5`.
### Clarifying Questions
The signs depend on the selected subsequence positions, not the positions in nums. The answer needs a 64-bit integer.
```hint Inspect the structure
What two states determine whether the next selected number receives a plus or minus sign?
```
### Reasoning checkpoints
- Respect the order of selected entries and assign signs by their positions in the subsequence rather than the original array.
- Prove the maximum score and account for the permitted value range and result width.
### Optional extensions
How would allowing negative entries affect the optimum and its proof?
Overview: Best Alternating Sum of an Ordered Selection. Choose a subsequence of the positive integers in nums, preserving their order, and reindex it starting at zero. Its score adds entries at even indices and subtracts entries at odd indices. Return the largest possible score.