題目給定的問題為：從索引 0 的位置開始，是否能到達最後一個位置的索引

## Solution

### Greedy

#### 解題方法

貪心解法，只關注局部最優解，不關注全局最優解

可以把當前索引看成前面走過的總步數，所以 **前面走過的總步數 (i) + 現在可以往後走的最大步數 (nums[i]) = 最遠可以走到的步數 (maxRech)**

因為不管怎麼樣都需要檢查所有的數字來計算是否可以走到最後一個索引，所以使用一個 for loop 來遍歷整個 array，並且每次紀錄 **最遠可以走到的步數 (macRech)**，如果這個數字等於或是超過 array.length 就代表可以走到最後一個位置的索引

#### 確保不會走超過最遠位置 (maxRech)

為了確保不會走超過最遠位置 (maxRech) 所能到達的位置，所以每次檢查當前下標是否大於所能到達的最遠位置 i > maxRech，如果超過，就代表不能走到最後一個位置了，可以直接返回 False

#### 小優化

如果最遠位置已經大於或者等於最後一個位置，直接返回 True，不需要等到整個 for loop 走完

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        maxRech = 0
        for i in range(len(nums)):
            if i > maxRech: # 如果最大步數到達不了當前下標，代表無法達到最後一個下標，直接返回
                return False
            maxRech = max(nums[i] + i,maxRech) # 紀錄從當前下標，可以往後走的最遠距離
            if maxRech >= len(nums):
                return True
        return True # 如果可以走到最後，就代表可以到達最後一個位置

2023.08.18 AC

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_can_reach = 0
        for i in range(len(nums)):
            if i > max_can_reach:
                return False
            max_can_reach = max(max_can_reach,i + nums[i])
        return True

### Complexity

- Time complexity: O(n)
- Space complexity: O(1)