最大的leftMax与rightMax之差的绝对值

import scala.io.StdIn

object Main {
    def main(args: Array[String]): Unit = {
        val in = StdIn
        val n = in.readInt()
        val arr = in.readLine().split(" ").map(_.toInt)
        if(n == 2){
            println(math.abs(arr(0) - arr(1)))
        }else{
            val leftMax = Array.ofDim[Int](n)      // 前缀最大值
            val rightMax = Array.ofDim[Int](n)     // 后缀最大值
            leftMax(0) = arr(0)
            rightMax(n - 2) = arr(n - 1)
            for(i <- 1 until n - 1)
                leftMax(i) = math.max(arr(i), leftMax(i - 1))
            for(i <- n - 3 to 0 by -1)
                rightMax(i) = math.max(arr(i + 1), rightMax(i + 1))
            var max = 0
            for(i <- 0 until n - 1)
                max = math.max(max, math.abs(leftMax(i) - rightMax(i)))
            println(max)
        }
    }
}

1. 全局最大值被分到了左边的数组，由于被划分的两部分数组都不能是空，因此右边的数组一定包括数组的最后一个值arr[n-1]。如果我们扩大右边的子数组，就会增加arr[n-1]之外的数，如果新增的数比它大，那么就会增加右边数组的最大值，从而减小右边数组最大值和左边数组最大值的绝对差；如果新增的数比它小，由于不会改变右边的最大值，所以并不会改变这个绝对差。因此，绝对差最大的情况与右边的数组只有arr[n-1]一个数的情况是等效的。
2. 同理可得，当全局最大值被分配到右边数组的时候，绝对差取得最大值的情况与左边的数组只有arr[0]一个数的情况是等效的。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(strArr[i]);
            max = Math.max(max, arr[i]);
        }
        System.out.println(Math.max(max - arr[0], max - arr[n - 1]));
    }
}