🧺 Space complexity: O(n), for the recursion stack.

Method 2 - Using Topdown DP Memoization

Intuition

Use memoization to avoid redundant calculations in the recursive approach. Store the maximum alternating sum for each subproblem defined by index and sign in a DP table.

Approach

Define a recursive function with a DP table indexed by position and sign. For each call, check if the result is already computed. If not, compute the maximum alternating sum by considering both choosing and skipping the current element, and store the result.

Code

[{"language":"C++","code":"class Solution {\npublic:\n\tlong long dfs(const vector<int>& nums, int idx, bool isPos, vector<vector<long long>>& dp) {\n\t\tif (idx == nums.size()) return 0;\n\t\tint posIdx = isPos ? 1 : 0;\n\t\tif (dp[posIdx][idx] != -1) return dp[posIdx][idx];\n\t\tlong long curr = isPos ? nums[idx] : -nums[idx];\n\t\tlong long choose = curr + dfs(nums, idx + 1, !isPos, dp);\n\t\tlong long skip = dfs(nums, idx + 1, isPos, dp);\n\t\tdp[posIdx][idx] = max(choose, skip);\n\t\treturn dp[posIdx][idx];\n\t}\n\tlong long maxAlternatingSum(vector<int>& nums) {\n\t\tvector<vector<long long>> dp(2, vector<long long>(nums.size(), -1));\n\t\treturn dfs(nums, 0, true, dp);\n\t}\n};","lang":"cpp"},{"language":"Go","code":"func maxAlternatingSum(nums []int) int64 {\n\tdp := make([][]int64, 2)\n\tfor i := range dp {\n\t\tdp[i] = make([]int64, len(nums))\n\t\tfor j := range dp[i] {\n\t\t\tdp[i][j] = -1\n\t\t}\n\t}\n\tvar dfs func(idx int, isPos bool) int64\n\tdfs = func(idx int, isPos bool) int64 {\n\t\tif idx == len(nums) {\n\t\t\treturn 0\n\t\t}\n\t\tposIdx := 0\n\t\tif isPos {\n\t\t\tposIdx = 1\n\t\t}\n\t\tif dp[posIdx][idx] != -1 {\n\t\t\treturn dp[posIdx][idx]\n\t\t}\n\t\tcurr := int64(nums[idx])\n\t\tif !isPos {\n\t\t\tcurr = -curr\n\t\t}\n\t\tchoose := curr + dfs(idx+1, !isPos)\n\t\tskip := dfs(idx+1, isPos)\n\t\tif choose > skip {\n\t\t\tdp[posIdx][idx] = choose\n\t\t} else {\n\t\t\tdp[posIdx][idx] = skip\n\t\t}\n\t\treturn dp[posIdx][idx]\n\t}\n\treturn dfs(0, true)\n}","lang":"go"},{"language":"Java","code":"public long maxAlternatingSum(int[] nums) {\n\tlong[][] dp = new long[2][nums.length];\n\tfor (int i = 0; i < 2; i++) Arrays.fill(dp[i], -1);\n\treturn dfs(nums, 0, true, dp);\n}\nprivate long dfs(int[] nums, int idx, boolean isPos, long[][] dp) {\n\tif (idx == nums.length) return 0;\n\tint posIdx = isPos ? 1 : 0;\n\tif (dp[posIdx][idx] != -1) return dp[posIdx][idx];\n\tlong curr = isPos ? nums[idx] : -nums[idx];\n\tlong choose = curr + dfs(nums, idx + 1, !isPos, dp);\n\tlong skip = dfs(nums, idx + 1, isPos, dp);\n\tdp[posIdx][idx] = Math.max(choose, skip);\n\treturn dp[posIdx][idx];\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n\tfun maxAlternatingSum(nums: IntArray): Long {\n\t\tval dp = Array(2) { LongArray(nums.size) { -1L } }\n\t\tfun dfs(idx: Int, isPos: Boolean): Long {\n\t\t\tif (idx == nums.size) return 0L\n\t\t\tval posIdx = if (isPos) 1 else 0\n\t\t\tif (dp[posIdx][idx] != -1L) return dp[posIdx][idx]\n\t\t\tval curr = if (isPos) nums[idx].toLong() else -nums[idx].toLong()\n\t\t\tval choose = curr + dfs(idx + 1, !isPos)\n\t\t\tval skip = dfs(idx + 1, isPos)\n\t\t\tdp[posIdx][idx] = maxOf(choose, skip)\n\t\t\treturn dp[posIdx][idx]\n\t\t}\n\t\treturn dfs(0, true)\n\t}\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n\tdef maxAlternatingSum(self, nums: list[int]) -> int:\n\t\tdp = [[-1] * len(nums) for _ in range(2)]\n\t\tdef dfs(idx: int, is_pos: bool) -> int:\n\t\t\tif idx == len(nums):\n\t\t\t\treturn 0\n\t\t\tpos_idx = 1 if is_pos else 0\n\t\t\tif dp[pos_idx][idx] != -1:\n\t\t\t\treturn dp[pos_idx][idx]\n\t\t\tcurr = nums[idx] if is_pos else -nums[idx]\n\t\t\tchoose = curr + dfs(idx + 1, not is_pos)\n\t\t\tskip = dfs(idx + 1, is_pos)\n\t\t\tdp[pos_idx][idx] = max(choose, skip)\n\t\t\treturn dp[pos_idx][idx]\n\t\treturn dfs(0, True)","lang":"python"},{"lan

Related Tags