想清楚了就真不难，个人认为比追忆略简单一点。
首先发现这个操作本质上就是告诉你可以合并一些数，感受一下会发现最后相当于保留一些数，使得每个数都能由一段区间转移过来，且这个区间内的数的贡献形式是 +-+-... 依次类推的。
接下来一个比较重要的观察是假设对于一个位置 \(x\)，由区间 \([l, r]\) 收缩得到，那么形式必然是 \(l \to x\)，\(r \to x\) 这样收缩，当然这也比较容易看出来。
进入正题，思考第一问，很显然的 \(O(n^3)\) 做法是设 \(f_i\)，每次枚举一个区间转移，再枚举区间内的一个点挖掉，看是否可行即可。然后思考 \(O(n^2)\) 做法，不难发现，最后可能得到的 \(k\) 一定是一个区间（可以预处理得到），但是区间内的数不一定都能取到，这是因为到了最后一步我们并不知道具体是哪边大哪边小，实际上打个表或者注意力强的可以观察到要么全取偶数，要么全取奇数，条件就是看上面那个 +-+-... 到底是 + 的多还是 - 的多。这个时候我们第一问就可以 \(O(n^2)\) 做了。
考虑为什么上述做法不能够直接套用在第二问的做法上，根本原因是因为如果有一段区间不能选择数（也就是全 \(0\)），那么可能会与其它情况本质相同，从而计重，而第一问我们是求解最优性问题所以没有关系，我们思考如何强化这个计数结构。其实也不难，将向左的操作更改为碰到第一个 \(a_j = 0\) 就停止就好，类似于我们单调栈跑区间处理相同数的问题。