我发现的问题

• 我的代码可以处理短输入，但不能处理长输入（测试用例1和2可以处理，但3花费的时间太多）
• 我相信代码可以优化（通过动态编程），但是如何优化呢？

猜猜看

• 递归限制问题（调用堆栈限制）可能发生在大规模输入中

前提条件

• 数组按升序排序
• 从当前编号= 0，k = 1开始
• k =与前一个数字的差值
• 下一个编号=当前编号+ k - 3
• 或下一个编号=当前编号+ k
• 或下一个编号=当前编号+ k + 1
• 或下一个编号=当前编号+ k + 2
• 如果nextNumber不在数组中，则它是路径的结尾
• nextNumber必须始终大于currentNumber
• 找到能达到的最大值
• 2〈=长度（arr）〈= 2000
• 0〈= arr[i]〈= 10^5
• arr[0] = 0，arr[1] = 1
• 空间限制：1024兆字节
• 时间限制：1秒

示例

测试用例1输入

7
0 1 2 3 8 9 11

测试用例1输出

3

测试用例2输入

8
0 1 3 5 6 8 12 17

测试用例2输出

17

测试用例3输入

80
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 27 28 29 31 32 33 35 37 39 40 41 43 44 45 48 49 50 53 54 57 58 61 63 67 68 73 74 79 80 83 85 90 91 94 96 101 103 109 111 120 122 130 131 132 155 160 165 170 175 176 177 190 200 250

测试用例3输出（预期）

175

编号

#include <iostream>
using namespace std;

int largestNumber = 0;

// search for a index at a given number
// search only bigger than given index
// given array is sorted
// return 0 if not found
int findIndex(int *numbers, int size, int target, int index)
{
    for (int i = index + 1; i < size; i++)
    {
        if (numbers[i] == target)
        {
            return i;
        }
    }
    return 0;
}

void findLargestNumberCanReach(int *numbers, int size, int k, int currentNumber, int currentIndex)
{
    if (currentIndex == size - 1) // reached to the end of the array
    {
        largestNumber = currentNumber;
        return;
    }
    else if (currentIndex == 0) // can't find next number
    {
        if (currentNumber - k > largestNumber) // last currentNumber is biggest
        {
            largestNumber = currentNumber - k;
        }
        return;
    }

    currentIndex = findIndex(numbers, size, currentNumber + (k - 3), currentIndex);
    findLargestNumberCanReach(numbers, size, k - 3, currentNumber + (k - 3), currentIndex);

    currentIndex = findIndex(numbers, size, currentNumber + (k), currentIndex);
    findLargestNumberCanReach(numbers, size, k, currentNumber + (k), currentIndex);

    currentIndex = findIndex(numbers, size, currentNumber + (k + 1), currentIndex);
    findLargestNumberCanReach(numbers, size, k + 1, currentNumber + (k + 1), currentIndex);

    currentIndex = findIndex(numbers, size, currentNumber + (k + 2), currentIndex);
    findLargestNumberCanReach(numbers, size, k + 2, currentNumber + (k + 2), currentIndex);

    return;
}

int main()
{
    int size;
    cin >> size;

    int *input = new int[size];
    for (int idx = 0; idx < size; idx++)
    {
        cin >> input[idx];
    }
    findLargestNumberCanReach(input, size, 1, 1, 1);
    cout << largestNumber << endl;

    delete[] input;
    return 0;
}