Algorithm too slow on large scale input case, and dynamic programming optimization

Question

Problems I found

My code works on short input but not on long input (test cases 1, and 2 work, but 3 takes too much time)
I believe code can be optimized (by dynamic programming), but how?

Guess

recursion limit problem(call stack limit) can occur in large scale input

Preconditions

the array is sorted in ascending order
starts with currentNumber = 0, k = 1
k = the difference to the previous number
nextNumber = currentNumber + k - 3
or nextNumber = currentNumber + k
or nextNumber = currentNumber + k + 1
or nextNumber = currentNumber + k + 2
if nextNumber is not in the array, it is the end of the path
nextNumber always has to be greater than currentNumber
find the biggest number that can reach

2 <= len(arr) <= 2000
0 <= arr[i] <= 10^5
arr[0] = 0, arr[1] = 1
space limit: 1024MB
time limit: 1sec

Examples

test case1 input

7
0 1 2 3 8 9 11

test case1 output

test case2 input

8
0 1 3 5 6 8 12 17

test case2 output

test case3 input

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

test case3 output(expected)

Code

#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;
}

*Problems I found* -- *Guess* -- You should be using a [debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems), then you wouldn't need to guess what is the issue. — PaulMcKenzie, Nov 23 '22 at 13:57
Or maybe it's just an exponential time algorithm. Each recursive call can lead to four more recursive calls. — john, Nov 23 '22 at 14:01
Recursive approach will always suffer from stack overflow for the big numbers. From the quick look, I can see that you can improve your search algorithm (do the binary search if array is sorted), and remove recursive calls, rewrite your algorithm to do iterative search. — pptaszni, Nov 23 '22 at 14:02
My compiler gives the expected result `175`, takes a while to get there but it does. I think this is just an inefficient algorithm. — john, Nov 23 '22 at 14:02
What is the logic for updating `k`? it is not mentioned in your question, only in your code. — Botje, Nov 23 '22 at 15:03
That space limit tells me that a bottom-up solution is expected. I still don't know what problem is trying to be solved, though. — sweenish, Nov 23 '22 at 15:29

score 1 · Accepted Answer · answered Nov 23 '22 at 20:10

This problem looks like a harder version of the LeetCode program "frog jump". Forget about the array or dynamic programming for a while and look at it conceptually. A state S is (n,k) where n is an element of the input array, and k the difference to the previous number. The initial state S0 is (0, 1).

Successor states (n', k') are then (n + k - 3, k - 3), (n + k, k), (n + k + 1, k + 1), (n + k + 2, k + 2), assuming that n' is an element of the array and n' > n.

States thus form a graph, and the question boils down to finding all successor states reachable from S0 and returning the state with the largest n.

In terms of C++, you need a couple of ingredients:

a std::set<int> in_array that tells whether a given number is part of the input array. This gives you O(log n) lookups. You could also use an std::unordered_set.
a type State that represents a state (n, k). You can use a struct or a std::pair<int, int>.
a std::set<State> seen that keeps track of visited states
a std::stack<State> todo that represents a list of states to visit

The main program is then a loop that takes an element from the stack and checks if the state has been visited already. If not, it marks the state as visited and adds the successors to the todo list.

When the stack becomes empty, take the highest element of seen. This is the largest array element reachable.

With all this, problem 3 without any extra compiler optimizations takes 30 ms on my system.