Readme

3660.Jump-Game-IX

此题乍看是个图论的问题，彼此可以跳转的点可以认为是联通的。但是构建所有的边需要n^2的复杂度。

我们定义preMax[i]表示前i个元素（包括自身）里的最大值。考察任意的rets[i]，如果答案只在左边的话，那么答案就是preMax[i]。但是也有可能答案在右边。从i能往右跳转到哪些地方呢？我们势必会先借助于preMax[i]，因为从preMax[i]跳转的话可以最大范围地覆盖到[i+1:n-1]里的可跳转区域。此时两种情况：

1. 如果preMax[i]<sufMin[i+1]，也就是说从preMax[i]也无法跳转到i右边的任何位置，于是rets[i]只能是preMax[i].

2. 如果preMax[i]>sufMin[i+1]，那么我们可以有这样一条跳转路径：i->preMax[i]->sufMin[i]->i+1. 最后一步跳转的依据是：根据定义，sufMin[i]是[i+1:n-1]里的最小值，必然小于等于nums[i+1].由此可知i与i+1是联通的，必然有rets[i]=rets[i+1].

由此我们发现了rets从后往前的递推关系。因为rets[n-1]必然等于preMax[n-1]，由此可以根据以上的结论，依次推出i=n-2,n-1,...,0的答案。