1911. Maximum Alternating Subsequence Sum
Approach
DP with two states (even/odd position sums); greedily add or skip each element.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
// Approach: DP with two states (even/odd position sums); greedily add or skip each element.
// Time: O(n) Space: O(1)
public class Solution
{
public long MaxAlternatingSum(int[] nums)
{
long even = 0; // the maximum alternating sum ending in an even index
long odd = 0; // the maximum alternating sum ending in an odd index
foreach (var num in nums)
{
even = Math.Max(even, odd + num);
odd = even - num;
}
return even;
}
}