055.cpp

// Given an array of non-negative integers, you are initially positioned at the first index of the array.
// Each element in the array represents your maximum jump length at that position.
// Determine if you are able to reach the last index.

// Example 1:
// Input: [2,3,1,1,4]
// Output: true
// Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

// Example 2:
// Input: [3,2,1,0,4]
// Output: false
// Explanation: You will always arrive at index 3 no matter what. Its maximum
//              jump length is 0, which makes it impossible to reach the last index.

#include <iostream> 
#include <vector>
using namespace std;

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int l = nums.size();
        int position = 0;
        while (nums[position] < l - 1 - position) {
            int greedy = 0;
            for (int k = 0; k <= nums[position]; k++) {
                if (greedy + nums[position + greedy] < k + nums[position + k])
                    greedy = k;
            }
            if (greedy == 0) return false;
            position += greedy;
        }
        return true;
    }
};