求最长等差数列和的非递归无数组实现问题求助

需要实现功能：输入序列长度n后逐个输入元素，返回最长等差数列的和；若多个数列长度相同，取和最大的，数列可增可减。要求不能使用数组、不能递归。现有测试代码存在以下问题：

• 数列差值变化时无法正确保存前一个数以计算新差值
• 前两个while循环冗余
• 代码未完成

现有测试代码 #

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
    int i, size, num, nextNum, diff, prevDiff, currSeqLength = 0, currSum, prevSum = 0;
    printf("Please enter the arithmetic list size: ");
    scanf_s("%d", &size);
    for (i = 1; i <= size; i++)
    {
        printf("Please enter num: ");
        scanf_s("%d", &num);
        while (i == 1)
        {
            prevSum = num;
            nextNum = num;
            currSeqLength++;
            break;
        }
        while (i == 2)
        {
            currSum = prevSum + num;
            diff = num - nextNum;
            nextNum = num;
            currSeqLength++;
            break;
        }
        while (i >= 3)
        {
            prevDiff = diff;
            diff = num - nextNum;
            nextNum = num;
            if (prevDiff == diff)
            {
                currSum += num;
                currSeqLength++;
                break;
            }
            else
            {
                prevDiff = diff;
                                // diff now should be the latest num - previous one
            }
        }
    }
}

核心改进思路 #

• 去掉冗余的while循环，用清晰的if分支处理前两个元素的初始化逻辑
• 增加前两个元素的跟踪变量，确保差值变化时能正确启动新的等差数列
• 全程维护全局最优结果：每次当前数列中断或遍历结束时，对比更新最长长度和对应最大和

修正后的代码 #

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main()
{
    int size, num;
    // 全局最优结果：最长长度、对应和
    int max_len = 0;
    long long max_sum = 0;
    // 当前等差数列状态：长度、和、差值，以及前两个元素
    int curr_len = 0;
    long long curr_sum = 0;
    int curr_diff = 0;
    int prev_prev_num, prev_num;

    printf("请输入序列长度: ");
    scanf_s("%d", &size);

    for (int i = 1; i <= size; i++)
    {
        printf("请输入第%d个元素: ", i);
        scanf_s("%d", &num);

        if (i == 1)
        {
            // 第一个元素初始化当前数列
            curr_len = 1;
            curr_sum = num;
            prev_num = num;
        }
        else if (i == 2)
        {
            // 第二个元素构建初始等差数列
            curr_len = 2;
            curr_sum += num;
            curr_diff = num - prev_num;
            prev_prev_num = prev_num;
            prev_num = num;
        }
        else
        {
            int new_diff = num - prev_num;
            if (new_diff == curr_diff)
            {
                // 差值匹配，延续当前等差数列
                curr_len++;
                curr_sum += num;
                prev_prev_num = prev_num;
                prev_num = num;
            }
            else
            {
                // 差值变化，先更新全局最优
                if (curr_len > max_len || (curr_len == max_len && curr_sum > max_sum))
                {
                    max_len = curr_len;
                    max_sum = curr_sum;
                }
                // 重置当前数列：从倒数第二个元素和当前元素开始
                curr_len = 2;
                curr_sum = prev_num + num;
                curr_diff = new_diff;
                prev_prev_num = prev_num;
                prev_num = num;
            }
        }

        // 实时检查当前数列是否为最优（处理最后一个数列未触发差值变化的情况）
        if (curr_len > max_len || (curr_len == max_len && curr_sum > max_sum))
        {
            max_len = curr_len;
            max_sum = curr_sum;
        }
    }

    // 单独处理序列长度为1的情况
    if (size == 1)
    {
        max_len = 1;
        max_sum = curr_sum;
    }

    printf("最长等差数列的长度为%d，和为%lld\n", max_len, max_sum);
    return 0;
}

代码说明 #

• 用prev_prev_num和prev_num跟踪前两个元素，确保差值变化时能正确初始化新的等差数列
• 用long long存储和，避免元素过多或数值过大导致的整数溢出
• 每次数列中断或遍历到末尾时都更新全局最优，不会遗漏最后一个数列
• 逻辑简化为清晰的分支判断，去掉无意义的循环包裹

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