Untitled

import java.util.Arrays;

public class Solution {
    public long maxAlternatingSum(int[] nums) {
        // Memoization table: -1 means not calculated yet
        long[][] memo = new long[nums.length][2];
        for (long[] row : memo) {
            Arrays.fill(row, -1);
        }
        // Start with the first index and even turn (true for even, false for odd)
        return dfs(nums, 0, true, memo);
    }

    private long dfs(int[] nums, int index, boolean flag, long[][] memo) {
        // Base case: If we've processed all elements
        if (index == nums.length) {
            return 0;
        }

        // Convert boolean `flag` to an integer (0 for even, 1 for odd) for memo indexing
        int flagIndex = flag ? 0 : 1;

        // If the result is already computed
        if (memo[index][flagIndex] != -1) {
            return memo[index][flagIndex];
        }

        // Skip the current element
        long skip = dfs(nums, index + 1, flag, memo);

        // Determine the value based on the flag
        long value = flag ? nums[index] : -nums[index];

        // Include the current element
        long take = value + dfs(nums, index + 1, !flag, memo);

        // Store the result in memo table and return the maximum of the two choices
        memo[index][flagIndex] = Math.max(skip, take);
        return memo[index][flagIndex];
    }
}