BinarySearch 0481 Largest Equivalent Set of Pairs

Problem statement

https://binarysearch.com/problems/Largest-Equivalent-Set-of-Pairs/

Solution

Equal to Leetcode 0956 Tallest Billboard.

Complexity

It is O(sn) for time and space, where s = sum(nums).

Code

class Solution:
    def solve(self, rods):
        n = len(rods)
        
        @lru_cache(None)
        def dfs(i, s):
            if i == -1:
                return 0 if s == 0 else float("-inf")
            return max(dfs(i - 1, s), dfs(i - 1, s - rods[i]), dfs(i - 1, s + rods[i]) + rods[i])
        
        return dfs(n - 1, 0)