Program.java

package AlgoExSolutions.Hard.MaximizeExpression;

// import java.util.*;

/**
 * * Maximize Expression
 */
class Program {
  /**
   * * TC: O(n)
   * * SC: O(4n) ~ O(n)
   */
  public int maximizeExpression(int[] array) {
    // Write your code here.
    int len = array.length;
    if (len < 4) return 0;

    int[] maxA = new int[len];
    maxA[0] = array[0];
    for (int i = 1; i < len; i++) maxA[i] = Math.max(maxA[i - 1], array[i]);

    int[] maxAMinusB = new int[len];
    maxAMinusB[0] = Integer.MIN_VALUE;
    for (int i = 1; i < len; i++)
      maxAMinusB[i] = Math.max(maxAMinusB[i - 1], maxA[i - 1] - array[i]);

    int[] maxAMinusBPlusC = new int[len];
    maxAMinusBPlusC[0] = maxAMinusBPlusC[1] = Integer.MIN_VALUE;
    for (int i = 2; i < len; i++)
      maxAMinusBPlusC[i] = Math.max(maxAMinusBPlusC[i - 1], maxAMinusB[i - 1] + array[i]);

    int[] maxAMinusBPlusCMinusD = new int[len];
    maxAMinusBPlusCMinusD[0] =
        maxAMinusBPlusCMinusD[1] = maxAMinusBPlusCMinusD[2] = Integer.MIN_VALUE;
    for (int i = 3; i < len; i++)
      maxAMinusBPlusCMinusD[i] =
          Math.max(maxAMinusBPlusCMinusD[i - 1], maxAMinusBPlusC[i - 1] - array[i]);

    return maxAMinusBPlusCMinusD[len - 1];
  }
}