无数组实现C语言最长递增子序列和求解技术咨询

需求 #

编写一个C语言函数，接收整数n及后续n个数字序列，返回最长连续等差子序列的和；若存在多个长度相同的最长子序列，取和较大的那个（根据示例，等差序列允许递增或递减）。

示例 #

• 示例1：n=8，序列为2,4,6,8,11,14,17,9 → 两个长度为4的子序列，输出和为50
• 示例2：n=2，序列7,19 → 输出和为26
• 示例3：n=8，序列8,6,4,2,11,14,15,16 → 最长子序列长度为4，输出和为20

现有问题 #

• 用数组实现该逻辑较简单，但无法想到无数组的实现方案
• 现有代码逻辑存在错误，寻求正确的无数组实现方法

现有错误代码 #

printf("please choose a n");
scanf("%d", &n);
y = n;
if (n == 1)
{
    printf("Please enter the next number ");
    scanf("%d", &series);
    return series;
}
else
    if (n == 2)
{
    while (i < 2) {
    {
        printf("Please enter the next number ");
            scanf("%d", &series);
            sum += series;
        }
        return sum;
    }
printf("Plase choose another number");
scanf("%d", &last);
sum += last;
printf("please choose another number");
scanf("%d", &series);
d = series - last;
sum = series + last;
bSum = sum;
for (i = 2; i < n; i++)
{
    last = series;
    printf("Please write another number; ");
    scanf("%d", &series);
     if (series - last == d)
      {
          sum += series;
          count++;
      }
      if (series - last != d)
      {
          if (count > length)
          {
              bSum = sum;
              length = count;
          }
          else if (count == length && sum > bSum)
          {
              bSum = sum;
          }
        }
}

核心思路 #

不需要存储整个序列，只需维护以下几个关键变量即可遍历一次完成计算：

• 前一个数（prev）、当前数（curr）
• 当前等差子序列的公差（curr_diff）、长度（curr_len）、和（curr_sum）
• 记录最优解的最长长度（max_len）、对应最大和（max_sum）

遍历过程中：

1. 每次读取新数后，计算当前差与当前子序列公差是否一致
2. 一致则延续当前子序列，更新长度和和
3. 不一致则结束当前子序列，与最优解比较更新，然后以当前两个数作为新子序列的起点
4. 遍历结束后，必须对最后一个子序列进行比较，避免遗漏

正确代码实现 #

#include <stdio.h>

int main() {
    int n;
    printf("请输入n的值: ");
    scanf("%d", &n);

    // 处理n=1的特殊情况
    if (n == 1) {
        int num;
        printf("请输入数字: ");
        scanf("%d", &num);
        printf("结果: %d\n", num);
        return 0;
    }

    int prev, curr;
    printf("请输入第1个数字: ");
    scanf("%d", &prev);
    printf("请输入第2个数字: ");
    scanf("%d", &curr);

    // 初始化最优解和当前序列的参数
    int max_len = 2;
    int max_sum = prev + curr;
    int curr_diff = curr - prev;
    int curr_len = 2;
    int curr_sum = max_sum;

    // 遍历剩余数字
    for (int i = 3; i <= n; i++) {
        int next_num;
        printf("请输入第%d个数字: ", i);
        scanf("%d", &next_num);

        int new_diff = next_num - curr;
        if (new_diff == curr_diff) {
            // 延续当前等差序列
            curr_len++;
            curr_sum += next_num;
        } else {
            // 结束当前序列，更新最优解
            if (curr_len > max_len) {
                max_len = curr_len;
                max_sum = curr_sum;
            } else if (curr_len == max_len && curr_sum > max_sum) {
                max_sum = curr_sum;
            }
            // 开启新的等差序列
            curr_diff = new_diff;
            curr_len = 2;
            curr_sum = curr + next_num;
        }
        // 更新前序数字指针
        prev = curr;
        curr = next_num;
    }

    // 最后一次比较，处理循环结束后未评估的当前序列
    if (curr_len > max_len) {
        max_len = curr_len;
        max_sum = curr_sum;
    } else if (curr_len == max_len && curr_sum > max_sum) {
        max_sum = curr_sum;
    }

    printf("结果: %d\n", max_sum);
    return 0;
}

代码说明 #

• 单独处理n=1的边界情况，直接返回唯一数字
• 初始化时读取前两个数，作为第一个等差子序列的起点
• 遍历过程中实时判断序列是否延续，及时更新当前序列参数
• 每次切换序列时立即与最优解比较，确保记录的是当前最优结果
• 遍历结束后补充一次比较，避免最后一个序列未被评估
• 全程仅使用有限变量，未使用任何数组存储整个序列

内容的提问来源于stack exchange，提问作者Guy