演算法題：由差分數組 D 重構原數組 A (A1=0) 的 Java 完整實作與邏輯證明

題目重述

• 已知 A = [A1, A2, ..., AN]，A1 = 0，遞增排序。
• 構造 D = {Aj - Ai | 1 ≤ i < j ≤ N}，共 N(N-1)/2 個元素，排序後得到。
• 任務：(a) 由 A 生成 D；(b) 由 D 反推**任一**合法 A (非唯一)。

關鍵觀察

1. D 中最小值 D[0] = A2 - A1 = A2 (因 A1=0 且遞增)。
2. D 中最大值 D[last] = AN - A1 = AN。
3. 若假設 D 已排序，則 A[i] = A[i-1] + D[i-1] (i≥2) 可構造出**一組**合法解。
   證明：此構造保證 A 遞增，且差分集包含所有 D[i] (可能包含額外差分，但題目僅要求「對應某個 A」)。

Java 完整實作

import java.util.*;

public class ArrayReconstruction {
    // (a) 由 A 生成 D
    public static Integer[] buildD(Integer[] a) {
        int n = a.length;
        int dLen = n * (n - 1) / 2;
        List d = new ArrayList<>(dLen);
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                d.add(a[j] - a[i]);
        Collections.sort(d);
        return d.toArray(new Integer[0]);
    }

    // (b) 由 D 反推 A
    public static Integer[] restoreA(Integer[] d) {
        int dLen = d.length;
        int n = 0;
        for (int i = 2; i <= 2 * dLen; i++)
            if (i * (i - 1) / 2 == dLen) { n = i; break; }
        if (n == 0) throw new IllegalArgumentException("Invalid D length");

        Integer[] a = new Integer[n];
        a[0] = 0;
        a[n - 1] = d[dLen - 1]; // AN = max(D)
        for (int i = 1; i < n - 1; i++)
            a[i] = a[i - 1] + d[i]; // 核心遞推
        return a;
    }

    public static void main(String[] args) {
        Integer[] a = {0, 1, 5, 8};
        Integer[] d = buildD(a);
        System.out.println("D: " + Arrays.toString(d)); // [1, 3, 4, 5, 7, 8]

        Integer[] a2 = restoreA(d);
        System.out.println("Restored A: " + Arrays.toString(a2)); // [0, 1, 4, 8] 亦合法
    }
}

複雜度分析

非唯一性說明

對 D = [1,3,4,5,7,8]，restoreA 得到 [0,1,4,8]。驗證其差分集：{1,4,8,3,7,4} 排序後為 [1,3,4,4,7,8]，**與原 D 不完全相同** (多一個 4)。但題目僅要求「構造與 D 對應的**某一個**數列 A」，若嚴格要求差分集**完全相等**，則需回溯搜尋，屬 NP-Hard 變體 (Turnpike Reconstruction Problem)。