Problem statement

https://binarysearch.com/problems/Sum-of-Three-Numbers-Trequel/

Solution

The idea is to look at the middle number. Then the right number should be as big as possible, we will keep suffix maximums for it. The left number should be as big as possible, but smaller than mid, for this we can use sorted list + binary search.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        ans = -float("inf")
        lft = SortedList(nums)
        rgh = -float("inf")

        for j in range(len(nums) - 1, 0, -1):
            mid = nums[j]
            lft.discard(mid)
            if mid <= rgh:
                i = lft.bisect_left(mid + 1) - 1
                if i != -1: ans = max(ans, lft[i] + mid + rgh)
            rgh = max(rgh, mid)

        return ans

Remark

There seems to be O(n) time complexity solution with stack, but I am not sure how it works yet.