Sum of Three Numbers Trequel - Google Top Interview Questions

                        Solution in C++ :

int solve(vector<int>& nums) {
    int res = 0, sz = nums.size();

    /*
     *   arr[i].first => some number in the number array
     *   arr[i].second => the corresponding index
     *   i.e. nums[ar[i].second] == ar[i].first
     */
    vector<pair<int, int>> arr;

    /*
     *   for each index i in the input(0 <= i < nums.length),
     *   larger[i] stores the number larger(or equal) than it on the right side.
     *   only numbers who have a larger/equal number to it on the right side can be the middle
     *   number a of valid triplet.
     */
    unordered_map<int, int> larger;

    // build the larger map for each index
    for (long long i = sz - 1, mx = INT_MIN - 1LL; i >= 0; --i) {
        if (mx >= nums[i]) larger[i] = mx;
        mx = max(mx, (long long)nums[i]);
        arr.push_back({nums[i], i});
    }

    sort(arr.begin(), arr.end());
    stack<int> st;

    /*
     * We have our array arr sorted by value(i.e. arr[i].first), now for each i,
     * we want to find a value such that it has smaller index in nums, it's value is smaller
     * but is as large as possible
     */
    for (int i = 0; i < sz; ++i) {
        auto [num, idx] = arr[i];
        if (larger.count(idx)) {
            while (!st.empty() && arr[st.top()].second > idx) st.pop();
            if (!st.empty()) res = max(res, nums[arr[st.top()].second] + num + larger[idx]);
            st.push(i);
        }
    }

    return res;
}
                    

                        Solution in Java :

import java.util.*;

class Solution {
    public int solve(int[] A) {
        int res = Integer.MIN_VALUE;
        int mx = Integer.MIN_VALUE;
        int maxs[] = new int[A.length];
        int B[] = new int[A.length];
        Arrays.fill(B, Integer.MIN_VALUE);

        for (int i = A.length - 1; i >= 0; i--) {
            mx = Math.max(mx, A[i]);
            maxs[i] = mx;
        }

        for (int i = A.length - 2; i >= 0; i--) {
            if (maxs[i + 1] >= A[i]) {
                B[i] = A[i] + maxs[i + 1];
            }
        }

        TreeSet<Integer> tree = new TreeSet<>();
        for (int i = 0; i < A.length; i++) {
            if (B[i] != Integer.MIN_VALUE) {
                Integer floor = tree.floor(A[i]);
                if (floor != null) {
                    res = Math.max(res, floor + B[i]);
                }
            }
            tree.add(A[i]);
        }

        return res;
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, nums):
        max_sum = -(2 ** 31)
        left_nums = SortedList(nums[:-1])
        right_num = nums[-1]

        for j in range(len(nums) - 2, 0, -1):
            mid_num = nums[j]
            left_nums.discard(mid_num)
            if mid_num <= right_num:
                i = left_nums.bisect_left(mid_num + 1) - 1
                left_num = left_nums[i]
                if left_num <= mid_num:
                    max_sum = max(max_sum, left_num + mid_num + right_num)

            right_num = max(right_num, mid_num)

        return max_sum