阿里云笔试阿里云笔试题算法岗 0511

笔试时间：2025年5月11日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：op 串问题

小红有一个长度为 n 的魔法环，环上依次有数字 a₁, a₂, …, aₙ 。她希望通过切开魔法环并对线性序列应用加权交替求和，得到最终魔法值。操作步骤如下：

选定一个断开位置 k (1 ≤ k ≤ n)，将环从此位置切开，得到线性序列 b₁ = aₖ, b₂ = aₖ₊₁, …, bₙ₋ₖ₊₁ = aₙ, bₙ₋ₖ₊₂ = a₁, …, bₙ = aₖ₋₁ 。对得到的线性序列 {bⱼ} 计算加权交替求和： S = 1・b₁ - 2・b₂ + 3・b₃ - 4・b₄ + … + (-1)ⁿ⁻¹n・bₙ 。

小红希望在所有可能的断开位置中，S 的值最大。请你计算并输出此最大值。

输入描述

第一行输入一个整数 n (1 ≤ n ≤ 2000)，表示魔法环上的数字个数。第二行输入 n 个整数 a₁, a₂, …, aₙ (0 ≤ aᵢ ≤ n)，代表环上各位置的初始数字。

输出描述

输出一个整数，表示小红在所有断开位置的加权交替求和中能获得的最大魔法值。

样例输入

4

1 2 3 4

样例输出

4

解释：当断开位置 k = 2 时，序列 [2, 3, 4, 1] 的加权交替求和为 2 - 6 + 12 - 4 = 4，这是所有 S 中的最大值。

参考题解

枚举所有可能的断开位置，生成线性序列后计算加权交替和，取最大值。

C++：

#include <iostream>
#include <vector>
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> b(2 * n);
    for (int i = 0; i < n; ++i) {
        b[i] = b[i + n] = a[i];
    }
    int max = -1e9;
    for (int k = 0; k < n; ++k) {
        int s = 0;
        int f = 1;
        for (int i = 0; i < n; ++i) {
            s += f * (i + 1) * b[k + i];
            f = -f;
        }
        if (s > max) {
            max = s;
        }
    }
    cout << max << endl;
    return 0;
}

Java：

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

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().trim());
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        // 构造 b 数组
        int[] b = new int[2 * n];
        for (int i = 0; i < n; i++) {
            b[i] = a[i];
            b[i + n] = a[i];
        }
        long max = Long.MIN_VALUE;
        for (int k = 0; k < n; k++) {
            long s = 0;
            int f = 1;
            for (int i = 0; i < n; i++) {
                s += (long)f * (i + 1) * b[k + i];
                f = -f;
            }
            if (s > max) {
                max = s;
            }
        }
        System.out.println(max);
    }
}

Python：

import sys

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    a = [int(next(it)) for _ in range(n)]
    # 构造 b 数组
    b = a + a

    max_val = -10**18
    for k in range(n):
        s = 0
        f = 1
        for i in range(n):
            s += f * (i + 1) * b[k + i]
            f = -f
        if s > max_val:
            max_val = s

    print(max_val)

if __name__ == "__main__":
    main()

第二题

给定一个时间序列数据，你的任务是计算并输出该序列的自相关函数。自相关函数的定义如下：对于一个时间序列 {Xₜ}，其自相关函数 ρ(h) 定义为： ρ(h) = E [(Xₜ₊ₕ - μ)(Xₜ - μ)] / σ² 其中，E [・] 表示期望，μ 是序列的均值，σ² 是序列的方差，h 是滞后（lag）。你需要写一个 Python 函数，接受一个由浮点数构成的列表作为输入，输出一个列表，列表中的第 i 个元素是输入序列的滞后 i 的自相关系数。你可以假设输入列表的长度至少为 2，且所有的输入数据都是有效的。（只能用python3）