笔试时间：2023年4月20日 春招实习

第一题

小红拿到了一个数组，她可以进行一次操作：选择两个相邻元素将它们合井，合并后的新元素为原来的两个元素之和。小红想知道，操作一次后数组的极差的最小值是多少？(数组的极差为:数组的最大值减最小值)

输入描述

第二行输入n个正整数ai，代表数组的元素。

2<=n<10^5

1<ai<10^9

输出描述

一个整数，代表操作后的极差最小值。

样例输入

3

1 4 5

样例输出

0

参考题解

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<int> pre_max(n);
    vector<int> pre_min(n);
    vector<int> suf_max(n);
    vector<int> suf_min(n);

    auto get_max = [&](int i) {
        int ret = a[i] + a[i + 1];
        if (i + 2 < n) {
            ret = max(ret, suf_max[i + 2]);
        }
        if (i - 1 >= 0) {
            ret = max(ret, pre_max[i - 1]);
        }
        return ret;
    };

    auto get_min = [&](int i) {
        int ret = a[i] + a[i + 1];
        if (i + 2 < n) {
            ret = min(ret, suf_min[i + 2]);
        }
        if (i - 1 >= 0) {
            ret = min(ret, pre_min[i - 1]);
        }
        return ret;
    };

    pre_max[0] = pre_min[0] = a[0];
    for (int i = 1; i < n; i++) {
        pre_max[i] = max(pre_max[i - 1], a[i]);
        pre_min[i] = min(pre_min[i - 1], a[i]);
    }

    suf_max[n - 1] = suf_min[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; i--) {
        suf_max[i] = max(suf_max[i + 1], a[i]);
        suf_min[i] = min(suf_min[i + 1], a[i]);
    }

    int ans = INT_MAX;
    for (int i = 0; i < n - 1; i++) {
        int mx = get_max(i);
        int mi = get_min(i);
        ans = min(ans, mx - mi);
    }

    cout << ans << endl;
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] a = new int[n];

        int[] pre_max = new int[n];
        int[] pre_min = new int[n];
        int[] suf_max = new int[n];
        int[] suf_min = new int[n];

        for (int i = 0; i < n; ++i) {
            a[i] = scanner.nextInt();
        }

        for (int i = 0; i < n; ++i) {
            pre_max[i] = pre_min[i] = a[i];
        }

        for (int i = 1; i < n; ++i) {
            pre_max[i] = Math.max(pre_max[i - 1], a[i]);
            pre_min[i] = Math.min(pre_min[i - 1], a[i]);
        }

        suf_max[n - 1] = suf_min[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            suf_max[i] = Math.max(suf_max[i + 1], a[i]);
            suf_min[i] = Math.min(suf_min[i + 1], a[i]);
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n - 1; ++i) {
            int mx = get_max(a, pre_max, suf_max, i);
            int mi = get_mi