最长等差数列的长度（进阶版——允许公差为零且包含负数，并统计不同最长等差数列的个数）

题目描述

给定一个整数数组 nums，请找出其中最长的等差数列的长度，并统计不同最长等差数列的个数。等差数列的公差可以是任意整数（包括零和负数），并且子序列可以不连续（即从原数组中删除一些元素后，剩余元素保持原有顺序构成等差数列）。注意，统计不同等差数列的个数时，只要元素在原数组中的位置序列（即下标序列）不同，即使元素值相同，也视为不同的等差数列。结果需要对 \(10^9 + 7\) 取模。

示例

输入: nums = [2, 4, 6, 8, 10]
输出: 长度=5, 个数=1
解释: 整个数组本身就是公差为2的等差数列，且是唯一的最长等差数列。

输入: nums = [7, 7, 7, 7, 7]
输出: 长度=5, 个数=1
解释: 公差为0，整个数组是等差数列，个数为1。

输入: nums = [1, 2, 3, 4, 5, 6]
输出: 长度=6, 个数=1
解释: 整个数组是公差为1的等差数列。

输入: nums = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5]
输出: 长度=5, 个数=2
解释: 最长等差数列是公差为1、长度为5的等差数列。有两个这样的子序列：前5个元素和后5个元素，它们下标序列不同，所以个数为2。

解题思路

这是一个线性动态规划问题，需要同时记录长度和个数。核心思想是利用动态规划表，其中 dp[i][d] 表示以第 i 个元素结尾、公差为 d 的等差数列的最长长度和对应的个数。但由于公差可能是负数且范围可能很大，我们需要一种有效的方式来存储公差。

关键难点

1. 公差可能非常大（例如数组中元素范围很大），不能直接用数组索引表示所有可能的公差。
2. 需要统计不同等差数列的个数，这意味着我们需要记录以每个位置 i 结尾、公差为 d 的所有等差数列的个数。
3. 对于每个位置 i，我们需要查看它之前的所有位置 j (j < i)，计算 diff = nums[i] - nums[j] 作为公差，然后更新以 i 结尾、公差为 diff 的状态。

优化方法
由于我们无法用数组直接索引所有可能的公差，我们可以使用一个字典（哈希表）来存储，其中键是公差，值是一个元组 (length, count)。对于每个位置 i，我们维护一个字典 dp[i]，表示以 nums[i] 结尾的所有公差对应的状态。

状态转移

• 对于每个 i，初始化 dp[i] 为一个空字典（或者默认包含一个长度为1、个数为1的“数列”，即单独一个元素）。
• 对于每个 j 从 0 到 i-1：
  • 计算公差 diff = nums[i] - nums[j]。
  • 在 dp[j] 中查找键为 diff 的状态，得到以 j 结尾、公差为 diff 的最长长度 len_j 和个数 cnt_j。如果不存在，则 len_j = 1（即单个元素 nums[j]），cnt_j = 1。
  • 那么，以 i 结尾、公差为 diff 的数列长度应为 len_j + 1，而数列的个数应等于 cnt_j（因为每个以 j 结尾的数列后面添加 nums[i] 就得到一个新的数列，且由于 nums[i] 固定，所以个数不变）。
  • 更新 dp[i][diff]：
    • 如果当前 dp[i][diff] 中记录的长度小于 len_j + 1，则更新长度为 len_j + 1，个数为 cnt_j。
    • 如果当前记录的长度等于 len_j + 1，则个数增加 cnt_j。
    • 如果当前记录的长度大于 len_j + 1，则忽略。

注意：当 len_j = 1 时，表示 j 位置之前没有形成以 diff 为公差的数列（即 nums[j] 是作为数列的第一个元素），此时形成的新数列长度为2，但个数依然为1（因为单个 nums[j] 接上 nums[i] 只形成一种数列）。

同时更新全局答案
在动态规划过程中，我们维护全局最长长度 max_len 和对应的总个数 total_count。每当更新 dp[i][diff] 时，如果新长度大于 max_len，则更新 max_len 并重置 total_count 为新个数；如果新长度等于 max_len，则将新个数加到 total_count 中。

复杂度分析

• 时间复杂度：O(n²)，其中 n 是数组长度，因为我们需要双重循环遍历所有 (j, i) 对。
• 空间复杂度：O(n²)，最坏情况下每个 dp[i] 字典可能存储 O(n) 个键（因为公差取决于之前所有元素），总共有 n 个位置。

边界情况

• 数组长度小于等于2时，整个数组本身就是等差数列，长度为 n，个数为1。
• 有重复元素时，公差为0的等差数列是允许的，但不同位置的相同值会形成不同的下标序列，因此个数会相应增加。

详细步骤

假设 nums = [2, 4, 6, 8, 10]，我们逐步演示动态规划过程。

1. 初始化

   • 创建一个列表 dp，长度为 n，每个元素是一个字典。
   • max_len = 1（至少一个元素），total_count = 0。
   • 遍历每个位置 i，我们先在 dp[i] 中放一个“虚拟”状态，表示长度为1的数列，但因为我们只关心长度>=2的数列，所以可以省略，或者最后将单个元素的情况统一处理。实际上，当没有找到任何 j 时，自然就认为长度为1。

2. 动态规划递推

   • i=0: 只有一个元素，dp[0] 为空（或者包含长度为1的状态）。max_len 保持1，由于只有一个元素，没有形成长度>=2的数列，total_count 暂时为0。
   • i=1: 检查 j=0，diff=2。dp[0] 中没有键2，所以以 j=0 结尾、公差2的长度为1，个数1。那么新数列长度=2，个数=1。更新 dp[1][2] = (2,1)。此时 max_len=2，total_count=1。
   • i=2:
     • j=0: diff=4，dp[0] 无键4，新数列长度=2，个数1。dp[2][4] = (2,1)。
     • j=1: diff=2，dp[1] 中有键2，长度为2，个数1。新数列长度=3，个数1。dp[2][2] = (3,1)。更新 max_len=3，total_count=1。
   • i=3:
     • j=0: diff=6，dp[3][6]=(2,1)
     • j=1: diff=4，dp[3][4]=(2,1)
     • j=2: diff=2，dp[2] 中有键2，长度3，个数1。新数列长度=4，个数1。dp[3][2]=(4,1)。max_len=4，total_count=1。
   • i=4:
     • j=0: diff=8，dp[4][8]=(2,1)
     • j=1: diff=6，dp[4][6]=(2,1)
     • j=2: diff=4，dp[4][4]=(2,1)
     • j=3: diff=2，dp[3] 中有键2，长度4，个数1。新数列长度=5，个数1。dp[4][2]=(5,1)。max_len=5，total_count=1。

3. 最终结果

   • 最后，max_len=5，total_count=1。

关于个数统计的进一步解释
注意，在状态转移时，个数是累加的。例如，如果有两个不同的 j1 和 j2，它们都能形成以 i 结尾、公差为 diff 且长度相同的数列，那么 dp[i][diff] 的个数应该是 cnt_j1 + cnt_j2。另外，如果同一个公差 diff 有不同的长度，我们只保留最长的长度及其对应的个数（因为题目要求的是最长等差数列的个数，不是所有长度等差数列的个数）。

取模
由于个数可能非常大，题目要求对 \(10^9+7\) 取模。我们在累加个数时进行取模即可。

最终答案
返回一个包含两个整数的列表或元组：[max_len, total_count % MOD]。注意，如果 max_len 为1（即数组所有元素都不构成长度>=2的等差数列），则 total_count 应为0，但题目可能要求返回0。但根据常见的变体题目，当最长长度为1时，个数通常为0，因为等差数列至少需要两个元素。这里我们约定，当最长长度<=2时，个数按上述逻辑统计（长度2的等差数列也统计个数）。

代码框架（Python风格）

def longestArithSeqLengthAndCount(nums):
    MOD = 10**9 + 7
    n = len(nums)
    if n <= 2:
        return n, 1  # 整个数组是等差数列，个数为1
    dp = [{} for _ in range(n)]  # dp[i][diff] = (length, count)
    max_len = 2
    total_count = 0
    
    for i in range(n):
        for j in range(i):
            diff = nums[i] - nums[j]
            # 从 dp[j] 中获取以 j 结尾、公差为 diff 的状态
            len_j, cnt_j = dp[j].get(diff, (1, 1))  # 如果不存在，长度为1，个数为1
            new_len = len_j + 1
            new_cnt = cnt_j
            # 更新 dp[i]
            if diff not in dp[i] or dp[i][diff][0] < new_len:
                dp[i][diff] = (new_len, new_cnt)
            elif dp[i][diff][0] == new_len:
                # 累加个数
                old_len, old_cnt = dp[i][diff]
                dp[i][diff] = (old_len, (old_cnt + new_cnt) % MOD)
            # 更新全局答案
            if new_len > max_len:
                max_len = new_len
                total_count = new_cnt
            elif new_len == max_len:
                total_count = (total_count + new_cnt) % MOD
    return max_len, total_count % MOD

注意事项

• 在实际代码中，由于我们初始化 len_j, cnt_j = dp[j].get(diff, (1, 1))，这意味着当 j 位置没有以 diff 为公差的数列时，我们将其视为长度为1、个数为1的数列，这样新数列长度就是2，个数为1，符合逻辑。
• 当数组中有重复元素时，公差为0的情况会被正确处理。例如 nums = [7,7,7]，当 i=2, j=1 时，diff=0，从 dp[1] 中得到长度2、个数1，新数列长度3、个数1。同时，i=2, j=0 也会产生长度2的数列，但因为我们只保留最长长度（3），所以不影响最终结果。

思考与扩展
本题的进阶要求是统计最长等差数列的个数，这比仅求长度更具挑战性，因为它需要在动态规划中维护额外的计数信息，并在状态转移时正确处理累加逻辑。通过这个例子，你可以更深入地理解动态规划中如何同时优化两个目标（最大长度和对应的方案数）。