I'm doing this problem https://leetcode.com/problems/maximum-alternating-subsequence-sum/ and attempting to change my code to use a matrix/array. I'm unable to figure out what the dimensions are. Drawing it out hasn't made it clear for me either and I think I'm missing a core concept or the recurrence relation. As far as I know, we either take an element or don't and when we do, we need to check whether we need to add it or subtract it.
I know the number of subsequences we can possibly have is 2^m where m = length of the sequence. So at worst the matrix is of size 2^m. But how can one accurately calculate the dimensions of the matrix here?
class Solution: def maxAlternatingSum(self, nums: List[int]) -> int: perms =  def dp(add, i, tmp): if i == len(nums): perms.append(tmp[:]) return 0 res = nums[i] taken = 0 not_taken = 0 if add: tmp.append(nums[i]) taken = res + dp(False, i + 1, tmp) tmp.pop() not_taken = dp(True, i + 1, tmp) else: tmp.append(res*-1) taken = (res * -1) + dp(True, i + 1, tmp) tmp.pop() not_taken = dp(False, i + 1, tmp) res = max(taken, not_taken) return res ans = dp(True, 0, ) print(perms, len(perms)) # num of subsequences is 2^length return ans ```