使用两层循环,枚举从每个元素 nums[i] 为起点开始的最长交替子序列长度。...在题解一中,我们会重复计算同一段交替子序列的,我们可以使用一次遍历,再交替子序列终止时避免重复回退到该子序列内部。...例如 [3,4,3,4,5,4,5] 数组,第一组交替子数组为 [3,4,3,4] 和第二组交替子数组为 [4,5,4,5] 这两组有重叠部分。...n^2)
一共 n 个分割点,每个分割点有「选和不选」两种方案,看起来总共有
2^n
种子状态,其实并没有。...剩下一个问题是怎么表示一个唯一的块,我们可以规定块中 4 个点中的其中一个点作为块的代表元(以右下角的点为例),然后将该点的行和列压缩到一个 Long 变量中来唯一标识不同的块。