1425. Constrained Subsequence Sum - Explanation

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        memo = [None] * len(nums)

        def dfs(i):
            if memo[i] != None:
                return memo[i]

            res = nums[i]
            for j in range(i + 1, len(nums)):
                if j - i > k:
                    break
                res = max(res, nums[i] + dfs(j))

            memo[i] = res
            return res

        ans = float('-inf')
        for i in range(len(nums)):
            ans = max(ans, dfs(i))
        return ans

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp = [num for num in nums]

        for i in range(1, len(nums)):
            for j in range(max(0, i - k), i):
                dp[i] = max(dp[i], nums[i] + dp[j])

        return max(dp)

class SegmentTree:
    def __init__(self, N):
        self.n = N
        while (self.n & (self.n - 1)) != 0:
            self.n += 1
        self.tree = [float('-inf')] * (2 * self.n)

    def update(self, i, val):
        i += self.n
        self.tree[i] = val
        while i > 1:
            i >>= 1
            self.tree[i] = max(self.tree[i << 1], self.tree[i << 1 | 1])

    def query(self, l, r):
        res = float('-inf')
        l += self.n
        r += self.n + 1
        while l < r:
            if l & 1:
                res = max(res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                res = max(res, self.tree[r])
            l >>= 1
            r >>= 1
        return max(0, res)

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        maxSegTree = SegmentTree(n)
        maxSegTree.update(0, nums[0])
        res = nums[0]

        for i in range(1, n):
            cur = nums[i] + maxSegTree.query(max(0, i - k), i - 1)
            maxSegTree.update(i, cur)
            res = max(res, cur)

        return res

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        res = nums[0]
        max_heap = [(-nums[0], 0)]  # max_sum, index

        for i in range(1, len(nums)):
            while i - max_heap[0][1] > k:
                heapq.heappop(max_heap)

            cur_max = max(nums[i], nums[i] - max_heap[0][0])
            res = max(res, cur_max)
            heapq.heappush(max_heap, (-cur_max, i))

        return res

class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dq = deque([(0, nums[0])])
        res = nums[0]

        for i in range(1, n):
            if dq and dq[0][0] < i - k:
                dq.popleft()

            cur = max(0, dq[0][1]) + nums[i]
            while dq and cur > dq[-1][1]:
                dq.pop()

            dq.append((i, cur))
            res = max(res, cur)

        return res