Leet Code #1425

1425. Constrained Subsequence Sum

This is my first: - Time trying to do this with Python

Lessons will be learned, and things will get easier

Iteration One

Goals

Working Solution for all edge cases
Nice integration with Jupyter notebook

Notes

Runtime and memory still feel abitrary - will try and focus on software engineering and algorithmic principles over runtime and memory until I do a much deeper dive.

from typing import List
import sys
from collections import deque

class Solution:
    def __init__(self):
        pass
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:

        # Start max at -\inf
        res = -sys.maxsize - 1
        q = deque()

        for i, num in enumerate(nums):
            # (if q) here detects if q is not empty
            # Try generate new max with current number
            total = num + q[0][1] if q else num
            res = max(res, total)

            while q and total >= q[-1][1]:
                q.pop()

            if total > 0:
                q.append((i, total))
            
            if q and q[0][0] == i - k:
                q.popleft()


        return res

# Lets try the solution defined above

inputs = [
    {"nums" : [10,2,-10,5,20], "k" : 2, "output" : 37},
    {"nums" : [-1,-2,-3], "k" : 1, "output" : -1},
    {"nums" : [10,-2,-10,-5,20], "k" : 2, "output" : 23}
]

tmp = Solution()

for input in inputs:
    output = tmp.constrainedSubsetSum(nums = input["nums"], k = input["k"])
    assert output == input["output"], f'Test failed for nums = {input["nums"]}, k = {input["k"]}. Expected = {input["output"]}, Returned = {output}'

Results

Not sure I really learned much here. Clearly dynamic programming is an area of growth for me, but this problem was tricky in how you used a deque and contructed the solution.

If it isn’t clear, I copied this solution from a refernce answer. I was getting close, but this solution is so elegant.