Problem statement

https://binarysearch.com/problems/Maximal-Expression/

Solution

Be careful, we can not use (-x) element like this. Let dp(i, j) be the minimum and maximum values for interval [i, j].

Complexity

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

Code

class Solution:
    def solve(self, nums):
        @lru_cache(None)
        def dp(i, j):
            if i == j: return (nums[i], nums[i])
            ans = [-float("inf"), float("inf")]
            cands = []
            for k in range(i, j):
                x1, x2 = dp(i, k)
                y1, y2 = dp(k + 1, j)
                cands += [x1*y1, x1*y2, x2*y1, x2*y2]
                cands += [x1+y1, x1+y2, x2+y1, x2+y2]
                cands += [x1-y1, x1-y2, x2-y1, x2-y2]
            return [min(cands), max(cands)]

        return dp(0, len(nums) - 1)[1]