You are given an integer array nums.

Your task is to choose three elements from the array—call them a, b, and c—located at distinct indices. Using these three chosen elements, you form the expression a + b - c.

The goal is to pick these three elements in a way that maximizes the value of the expression a + b - c.

Return an integer representing the maximum possible value that this expression can reach.

To put it simply:

• You need exactly three different positions in the array (the indices must be distinct, though the values themselves could repeat).
• a and b are added together, while c is subtracted.
• To make a + b - c as large as possible, you want a and b to be the two largest values available, and c to be the smallest value available.

For example, if nums = [1, 3, 6, 2, 4], the two largest values are 6 and 4, and the smallest value is 1. The maximum expression value would be 6 + 4 - 1 = 9.

The expression we want to maximize is a + b - c. Looking at this expression, we can break it into two separate goals that don't interfere with each other:

• We want a + b to be as large as possible.
• We want c to be as small as possible (since c is subtracted, a smaller c makes the result bigger).

Since a and b are added together, the way to make their sum as large as possible is to pick the two largest values in the array. Meanwhile, to subtract as little as possible, we should pick the smallest value in the array for c.

A natural worry here is the constraint that the three indices must be distinct. But because the array provides separate positions, the two largest elements and the smallest element will always sit at different indices—even if some of these values happen to be equal, they come from different positions in the array. So as long as the array has at least three elements, we can always assign a, b, and c to three distinct indices without conflict.

This means we don't need to try every combination of three elements. Instead, a single pass through the array is enough: we just keep track of the largest value, the second largest value, and the smallest value as we go. Once we have these three numbers, the answer is simply a + b - c.

Pattern Learn more about Greedy and Sorting patterns.

Solution 1: Find Maximum, Second Maximum, and Minimum Values

Based on the intuition, we only need three pieces of information from the array: the largest value a, the second largest value b, and the smallest value c. With these, the answer is just a + b - c.

We can gather all three in a single pass through the array, which keeps the algorithm efficient.

We start by initializing three variables:

• a = -inf and b = -inf to track the two largest values (we start them at negative infinity so any real number will be larger).
• c = inf to track the smallest value (we start it at positive infinity so any real number will be smaller).

Then, for each element x in nums, we perform two checks:

1. Update the minimum: If x < c, then x is smaller than the current smallest value, so we update c = x.

2. Update the top two maximums: This needs a little care to keep a as the largest and b as the second largest:

   • If x >= a, then x is at least as big as the current largest. The old a becomes the new second largest, so we do a, b = x, a. This shifts the previous maximum down into b and places x as the new maximum.
   • Otherwise, if x > b, then x isn't bigger than a but is bigger than the current second largest, so we update b = x.

After scanning the whole array, a and b hold the two largest values and c holds the smallest value. We return a + b - c.

The Python implementation:

class Solution:
    def maximizeExpressionOfThree(self, nums: List[int]) -> int:
        a = b = -inf
        c = inf
        for x in nums:
            if x < c:
                c = x
            if x >= a:
                a, b = x, a
            elif x > b:
                b = x
        return a + b - c

Complexity Analysis:

• Time Complexity: O(n), where n is the length of nums. We traverse the array only once.
• Space Complexity: O(1), since we only use a constant number of variables regardless of the input size.