Problem statement

https://leetcode.com/problems/tallest-billboard/

Solution 1

What we need to find is sum of some elements equal to zero, where we can take elements with 0, num, -num for each number.

First idea is to use the meed in the middle idea, where we split data into two parts and for each part we will keep the following date (sum of all taken elements, difference between first and second steel supports. To generate all date, we use dfs(i, j, sm, gain, out)` function, where:

  1. i is the index of current bar.
  2. j is the index of last bar we want to take.
  3. f is sum of all taken elements so far, (this sum can have negative elemens)
  4. s is the height of the left bar.
  5. out is the output array, where we keep results.

Then what we do is run dfs for left and right parts and then for each key in the first dictionary, check if -key is in the second dictionary. For these pair we evaluate d1[key] + d2[-key] and find the maximum among candidates.

Complexity

It is O(3^(n//2)) for time and the same for space.

Code

class Solution:
    def tallestBillboard(self, R):
        p1, p2, ans, n = {}, {}, 0, len(R)
    
        def dfs(i, j, f, s, out):
            if i == j:
                out[f] = max(out.get(f, 0), s)
                return
            dfs(i+1, j, f, s, out)
            dfs(i+1, j, f + R[i], s + R[i], out)
            dfs(i+1, j, f - R[i], s, out)
        
        dfs(0, n//2, 0, 0, p1)
        dfs(n//2, n, 0, 0, p2)
        
        for key, val1 in p1.items():
            if -key in p2:
                ans = max(ans, val1 + p2[-key])
                
        return ans

Solution 2

Similar logic can be applied, but now state is (i, s), where i is index of bar, s is taken sum (with positive and negative numbers) dfs(i, s) answer the question: what is maximum height of the left pillar if we have two pillars with sum s. Then we have 3 options:

  1. If we do not take bar, we have dfs(i - 1, s) option.
  2. If we put bar to the right pillar, we have dfs(i - 1, s - rods[i]).
  3. If we put bar to the left pillar, we have dfs(i - 1, s + rods[i]) + rods[i]

Complexity

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

Code

class Solution:
    def tallestBillboard(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)