class Solution {
typedef long long ll;
public:
long long maxAlternatingSum(vector<int>& nums) {
int n = nums.size();
vector<ll> dpPos(n, 0);
vector<ll> dpNeg(n, 0);
dpPos[0] = nums[0];
dpNeg[0] = 0;
for(int i = 1; i < n; ++i) {
dpPos[i] = max(dpPos[i-1], dpNeg[i-1] + nums[i]);
dpNeg[i] = max(dpNeg[i-1], dpPos[i-1] - nums[i]);
}
return max(dpPos[n-1], dpNeg[n-1]);
}
};
// 6,2,1,2,4,5
// 3 options, add, minus, make a number 0
// op: 0, 1, 2
// dp[op][i]: the maximum until i for the operation
// add: dp[0][i] = max(dp[1][i-1] + nums[i], dp[0][i-1], dp[2][i-1] + nums[i])
// we may don't take a number, we still have to do according to the last number taken
// dp[op][i]: op is the last operation took until i
// + -
// X X X X X [X] X [X]
