0
$\begingroup$

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
```
$\endgroup$
2
  • 1
    $\begingroup$ Coding questions are off-topic. Any question that requires us to read your code is likely off-topic here. Please replace the code with concise pseudocode (which doesn't require us to know any particular programming language and doesn't require us to read 20 lines of code). $\endgroup$
    – D.W.
    Dec 29 '21 at 23:33
  • 1
    $\begingroup$ Also, it is not clear to me what you are asking. Please make sure the question is self-contained, so we don't have to click on a link to understand what you're asking. (Also we want the question to remain useful even if the link stops working.) It's not clear how you plan to use a matrix or array so I'm not sure whether we're going to be able to tell you what dimensions to make it. $\endgroup$
    – D.W.
    Dec 29 '21 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.