贪心算法适用于跳跃游戏I和II，但不适用于最大子数组和问题；后者需用动态规划（Kadane算法），因其依赖状态转移而非局部最优选择。

贪心算法在跳跃游戏问题中非常适用，但在最大子数组和问题中并不适用——后者标准解法是动态规划（Kadane 算法），不是贪心。这一点容易混淆，需要先厘清。

跳跃游戏 I：判断能否到达终点

核心是维护“当前能到达的最远下标”，每一步都用当前位置所能跳到的最远位置去更新这个边界。

• 初始化 maxReach = 0，表示起始时最远只能到索引 0
• 遍历数组，对每个索引 i，若 i > maxReach，说明已断连，直接返回 false
• 否则更新：maxReach = Math.max(maxReach, i + nums[i])
• 一旦 maxReach >= nums.length - 1，可立即返回 true

跳跃游戏 II：求最少跳跃次数

本质是模拟 BFS 的层级扩展，但不用队列，靠两个边界变量推进：

Alibabacloud Sdk Client Initialization For Java

在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

• currentEnd：当前跳跃步数下能覆盖的最右索引
• farthest：下一步跳跃能到达的最远索引
• jumps：已执行的跳跃次数
• 遍历到 n-2 即可（最后位置不需再跳）；每当 i == currentEnd，就不得不跳一次，jumps++ 并更新 currentEnd = farthest
• 更新 farthest 时始终取 Math.max(farthest, i + nums[i])

为什么最大子数组和不能用贪心？

贪心要求每步选择局部最优后，全局仍最优，且不可撤销。但最大子数组和中，“舍弃前面负和”看似像贪心，实际依赖的是状态转移：是否延续前序和，取决于前序和是否为正——这本质是动态规划的递推关系（dp[i] = max(nums[i], dp[i−1] + nums[i])）。

• 没有单一“当前最优选择”能独立决定全局结果
• 比如 [-2,1,-3,4,-1,2,1,-5,4]，不能靠某次“选最大数”或“跳过负数”直接得出答案
• Kadane 算法虽代码简洁，但逻辑基础是状态继承，不是贪心选择性质

常见误区提醒

写跳跃游戏代码时，这几个细节极易出错：

• 数组长度为 1 时，Jump Game I 直接返回 true，II 返回 0
• Jump Game II 中，不要在 i == n−1 时更新 farthest，避免越界或误增跳跃
• 更新 currentEnd 后应立刻检查是否 ≥ n−1，防止多跳一次
• 遍历范围控制：Jump Game I 是 i ≤ maxReach，II 是 i < n−1