T4 T2的plus版，思想是一样的。两个长为n的数组，同位置元素可以交换。要求两数组各自的差值数组之和加起来最大，求最小的交换次数。首先注意我们的主要目标是差值数组之和最大，交换次数最小只是其次。同样使用动态规划，sums_n, sums_y分别表示末尾元素保持原位置和交换的情况下最大的差值数组之和，cnts_n, cnts_y对应二者的交换次数。设join_n， join_y分别是当前元素保持原位置和交换的情况下和上一个元素的差值之和，那么根据上一个元素是否交换，有转移方程 sums_n = max(sums_n + join_n, sums_y + join_y) sums_y = max(sums_n + join_y, sums_y + join_n) 而cnts_n, cnts_y跟着赋值即可，如果括号里二者相等，在优先选择交换次数较小的。 注意sums_n/sums_y逻辑上同时计算，使用临时变量避免前者的计算影响后者。 时间复杂度O(n)，空间复杂度O(1)。