LongJumps.cpp

LongJumps.cpp

int solution(vector<int> a) {
    int n = a.size();

    vector<int> dp(n, 0); // init array of size n to 0
    
    int mx = 0; // find max dp value

    for (int i = n - 1; i > -1; i--) { // loop backwards from a
        
        int t = a[i]; // this DP value

        int nextIndex = i + a[i]; // see if DP value from next jump exists

        if (nextIndex < n) {
            t += dp[nextIndex]; // DP value exists, add to this DP value
        }

        dp[i] = t; // set DP value

        mx = max(mx, dp[i]); // take the max dp value found
    }

    return mx;
}