Untitled
unknown
plain_text
2 months ago
1.4 kB
2
Indexable
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]; } }
Editor is loading...
Leave a Comment