Maximize Expression of Three Elements - Solution & Explanation

Problem Overview: You are given an array and need to maximize the value of an expression formed using three different elements. The indices must be distinct, and the goal is to choose the combination of numbers that produces the largest possible value.

Approach 1: Enumeration (Brute Force) (Time: O(n^3), Space: O(1))

The most direct strategy checks every valid triplet of indices (i, j, k). Iterate through the array with three nested loops and compute the expression for each combination. Track the maximum value seen so far. This approach guarantees correctness because it evaluates all possibilities, but it quickly becomes impractical for large arrays due to cubic time complexity. It’s useful as a baseline when first reasoning about the problem.

Approach 2: Sorting the Array (Time: O(n log n), Space: O(1) or O(n) depending on implementation)

Sorting the array helps reveal which values contribute most to the expression. Since the maximum result often comes from combining the largest elements with the smallest one, you can sort the array and evaluate only a few candidate combinations such as the largest two values with the smallest value. Sorting reduces the search space dramatically compared to brute force. This approach relies on the observation that extreme values dominate the expression.

Approach 3: Track Maximum, Second Maximum, and Minimum (Greedy) (Time: O(n), Space: O(1))

The optimal solution scans the array once while tracking three key values: the maximum element, the second maximum element, and the minimum element. These values are sufficient because the expression becomes largest when the positive contribution is maximized and the subtractive component is minimized. During a single pass, update these three variables using simple comparisons. After the scan, compute the expression using these extremes. This greedy observation removes the need for sorting or enumeration.

This solution is a classic pattern when working with Array problems: the optimal answer often depends only on a few extreme values. The reasoning also overlaps with Greedy strategies where local optimal choices lead to the global optimum, and sometimes with Sorting when extremes must be identified.

Recommended for interviews: The greedy single-pass approach. Start by explaining the brute force enumeration to demonstrate understanding of the constraints, then derive the insight that only the maximum, second maximum, and minimum elements affect the result. Interviewers expect the final O(n) time and O(1) space solution.