55. Jump Game

problem description

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.

algorithm thought

和之前jump game2类似。这里不限制你跳跃的次数，我们只需要每次记录能达到的最远距离即可。每次循环开始的时候更新最大值。如果更新之后的最大值和当前值是一样的话，说明只能跳到这里了，return false。如果所有的跳完，return true

code

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxrive=0;
        for(int i=0;i<nums.size()-1;++i){
            maxrive=max(maxrive,nums[i]+i);
            if(maxrive==i)
                return false;
        }
        return true;
    }
};

algorithm analysis

算法遍历一次数组，时间复杂度O(n)。