Maximize Expression

Tags

Maximize Expression

Category

Dynamic Programming

Difficulty

Hard

Problem Statement

Given an array of integers, find four indices a < b < c < d that maximize the expression A[a] - A[b] + A[c] - A[d]. Return the maximum value of this expression.

Intuition

A brute-force search over all four-index combinations is O(n^4). We can decompose the expression into a chain of decisions built left to right. If we know the best value of A[a] for all positions up to some index, we can efficiently compute the best of A[a] - A[b], then A[a] - A[b] + A[c], and finally A[a] - A[b] + A[c] - A[d]. Each stage only depends on the previous stage's running maximum.

Approach

  1. Create four arrays (or running variables), each of length n:
    • maxA[i] = max of A[j] for j in [0, i]
    • maxAB[i] = max of A[a] - A[b] for a < b <= i
    • maxABC[i] = max of A[a] - A[b] + A[c] for a < b < c <= i
    • maxABCD[i] = max of A[a] - A[b] + A[c] - A[d] for a < b < c < d <= i
  2. Fill them left to right:
    • maxA[i] = max(maxA[i-1], A[i])
    • maxAB[i] = max(maxAB[i-1], maxA[i-1] - A[i])
    • maxABC[i] = max(maxABC[i-1], maxAB[i-1] + A[i])
    • maxABCD[i] = max(maxABCD[i-1], maxABC[i-1] - A[i])
  3. Return maxABCD[n-1].

Pseudocode

function maximizeExpression(array):
    n = length(array)
    if n < 4: return -INFINITY    // not enough elements

    maxA    = array of size n
    maxAB   = array of size n
    maxABC  = array of size n
    maxABCD = array of size n

    maxA[0] = array[0]
    for i from 1 to n-1:
        maxA[i] = max(maxA[i-1], array[i])

    maxAB[0] = -INFINITY
    for i from 1 to n-1:
        maxAB[i] = max(maxAB[i-1], maxA[i-1] - array[i])

    maxABC[0] = maxABC[1] = -INFINITY
    for i from 2 to n-1:
        maxABC[i] = max(maxABC[i-1], maxAB[i-1] + array[i])

    maxABCD[0] = maxABCD[1] = maxABCD[2] = -INFINITY
    for i from 3 to n-1:
        maxABCD[i] = max(maxABCD[i-1], maxABC[i-1] - array[i])

    return maxABCD[n-1]

Time & Space Complexity

MeasureComplexityJustification
TimeO(n)Four linear passes over the array
SpaceO(n)Four auxiliary arrays (can be reduced to O(1) with four running variables)

Key Insights

  • The technique generalizes to any fixed-length alternating-sign expression. For k terms, build k layers, each in O(n), yielding O(kn) total.
  • Each layer encodes "the best partial expression ending at or before index i," which is why each layer references layer[i-1] (ensuring strict index ordering).
  • The space can be reduced to O(1) by maintaining just four running maximums if we compute all layers in a single pass from left to right (each layer at index i depends on the previous layer at index i-1).

Edge Cases

  • Array has fewer than 4 elements: impossible to form the expression; return an error or -infinity.
  • All elements are identical: the expression evaluates to 0.
  • Array is sorted ascending: A[a] should be large and A[d] small, but the index ordering constraint a < b < c < d complicates naive greedy selection.
  • Negative numbers: the algorithm handles them naturally since it tracks maximums at each stage.

Linked mentions