Difficulty:4.4(青下位)/ Easy
简单典题。
定义 dpidp_idpi 为 iii 结尾的答案。注意到转移时要动态维护 maxA[j,i]−minA[j,i]\max A_{[j,i]}-\min A_{[j,i]}maxA[j,i] −minA[j,i] ,考虑对 max\maxmax 和 min\minmin 上个单调栈,区间 chkmax / chkmin 相当于区间加减,上个线段树优化即可。
时间复杂度:O(nlogn)O(n\log n)O(nlogn)。