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

3

---

test case2 input

8
0 1 3 5 6 8 12 17

test case2 output

17

---

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)

175

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

Answer 1

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.