小红的等差数列

[题目链接](https://www.nowcoder.com/practice/425cf859f39e4012a7436b5729ff0b10)

思路

题目要求删除最少数字使数组变成等差数列。等价于：在原数组中找最长的等差子序列，删除的数量即为 $n$ 减去该子序列长度。

最长等差子序列 DP

定义 $dp[i][d]$ 为以第 $i$ 个元素结尾、公差为 $d$ 的最长等差子序列长度。

状态转移：枚举每个 $j < i$ ，令 $d = a[i] - a[j]$ ，则：

$ $dp[i][d] = dp[j][d] + 1$ $

若 $dp[j][d]$ 不存在，视为 1（只有 $a[j]$ 本身），则 $dp[i][d] = 2$ 。

最终答案为 $n - \max_{i,d} dp[i][d]$ 。

由于公差 $d$ 的范围可能很大，用哈希表（unordered_map）存储每个位置的状态。

边界情况

$n \leq 2$ 时，任意数组都是等差数列，直接输出 0。
最长子序列长度至少为 1（单个元素），所以最多删除 $n-1$ 个。

复杂度分析

时间复杂度： $O(n^2)$ ，双重枚举 $i$ 和 $j$ ，哈希表操作均摊 $O(1)$ 。
空间复杂度： $O(n^2)$ ，最坏情况下所有公差各不相同。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    if (n <= 2) {
        cout << 0 << endl;
        return 0;
    }

    // dp[i][d] = 以 a[i] 结尾、公差为 d 的最长等差子序列长度
    vector<unordered_map<int,int>> dp(n);
    int maxLen = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int d = a[i] - a[j];
            int prev = dp[j].count(d) ? dp[j][d] : 1;
            int cur = prev + 1;
            if (!dp[i].count(d) || dp[i][d] < cur) {
                dp[i][d] = cur;
            }
            maxLen = max(maxLen, dp[i][d]);
        }
    }

    cout << n - maxLen << endl;
    return 0;
}

import java.util.*;
import java.io.*;

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());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }

        if (n <= 2) {
            System.out.println(0);
            return;
        }

        // dp[i] 是从差值 d 到子序列长度的映射
        @SuppressWarnings("unchecked")
        HashMap<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
        }

        int maxLen = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int d = a[i] - a[j];
                int prev = dp[j].getOrDefault(d, 1);
                int cur = prev + 1;
                dp[i].put(d, Math.max(dp[i].getOrDefault(d, 1), cur));
                maxLen = Math.max(maxLen, dp[i].get(d));
            }
        }

        System.out.println(n - maxLen);
    }
}