4.20 蚂蚁笔试

1. 数组合并两个元素，找极差
1. 题目：拿到一个数组，可以进行一次合并（把相邻两个数合并得到新元素）。计算新合并后，数组内 “最大值和最小值的差”
2. 用例： (1) 例子1： 3 （换行）1 4 5 (2) 例子2： 4（换行） 9 1 3 6
3. 解法2：动态dp。 根据刚刚大佬的思路分享，重写了动态dp的解法。

import java.util.Scanner;

// 解法2：动态dp
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);     
        while (in.hasNextInt()) {
            int n = in.nextInt();
            long[] numsArr = new long[n+1];
            long[] iPreMinDp = new long[n+2]; long[] iAftMinDp = new long[n+2];
            long[] iPreMaxDp = new long[n+2]; long[] iAftMaxDp = new long[n+2];   
            iPreMaxDp[0]=Integer.MIN_VALUE; iAftMaxDp[n+1]=Integer.MIN_VALUE;
            iPreMinDp[0]=Integer.MAX_VALUE; iAftMinDp[n+1]=Integer.MAX_VALUE; 

            // 1.维护 [1,i] 范围的 min、max 动态dp
            for(int i=1; i<=n; i++){
                numsArr[i] = in.nextLong();               
                iPreMaxDp[i] = Math.max(iPreMaxDp[i-1], numsArr[i]);
                iPreMinDp[i] = Math.min(iPreMinDp[i-1], numsArr[i]);
            }
            // 2.维护 [i,n] 范围的 min、max 动态dp
            for(int i=n; i>=1; i--){
                iAftMaxDp[i] = Math.max(iAftMaxDp[i+1], numsArr[i]);
                iAftMinDp[i] = Math.min(iAftMinDp[i+1], numsArr[i]);
            }
            
            // 3.合并算极差
            long resMinCha = Integer.MAX_VALUE;
            for(int i=1; i<=n-1; i++){
                // 3.1、合并
                long temCounter = numsArr[i]+numsArr[i+1];
                // 3.2、算极差
                //     （1）合并后max：max(合并后元素， i-1及之前的最大， i+2及之后的最大)
                //     （2）合并后min：min(合并后元素， i-1及之前的最小， i+2及之后的最小)
                long maxNum = Math.max(temCounter, Math.max(iPreMaxDp[i-1], iAftMaxDp[i+2]));
                long minNum = Math.min(temCounter, Math.min(iPreMinDp[i-1], iAftMinDp[i+2]));
                resMinCha = Math.min(resMinCha, maxNum-minNum);
            }
            System.out.println(resMinCha);
        }
    }
}