重排数组B满足A的相邻顺序反转并最大化绝对相邻和

核心思路 #

先根据数组A的相邻关系确定数组B必须满足的相邻约束序列，再通过排序+动态规划的方式，在满足约束的前提下最大化相邻元素的绝对值之和。整体时间复杂度为O(n log n)，能适配N≤1e5的规模。

步骤详解 #

1. 生成约束序列 #

遍历数组A，生成op数组，明确B的相邻元素必须满足的关系：

• 若A[i] > A[i+1]，则op[i] = 1，要求B[i] < B[i+1]（A的降序对应B的升序）
• 若A[i] < A[i+1]，则op[i] = -1，要求B[i] > B[i+1]（A的升序对应B的降序）

2. 排序数组B #

将数组B从小到大排序为sorted_B，通过双指针从两端选取元素，能最大化相邻元素的差值。

3. 动态规划求解最大和 #

用两个变量跟踪状态（无需维护完整数组，优化空间至O(1)）：

• prev_left：处理到前一个元素时，选取当前可用区间左端点（未选的最小元素）的最大和
• prev_right：处理到前一个元素时，选取当前可用区间右端点（未选的最大元素）的最大和

初始化：
第一个元素无相邻元素，prev_left = 0（选sorted_B[0]），prev_right = 0（选sorted_B[n-1]），同时初始化双指针l=0，r=n-1。

状态转移：
遍历i从1到n-1：

• 当op[i-1] = 1（要求B[i-1] < B[i]）：
  • 只能从prev_left转移到当前右端点：curr_right = prev_left + (sorted_B[r] - sorted_B[l])，随后r -= 1
  • 也可从prev_left转移到当前左端点：curr_left = prev_left + (sorted_B[l+1] - sorted_B[l])，随后l += 1，但此路径总和必然小于选右端点的情况，可优先记录最大值
• 当op[i-1] = -1（要求B[i-1] > B[i]）：
  • 只能从prev_right转移到当前左端点：curr_left = prev_right + (sorted_B[r] - sorted_B[l])，随后l += 1
  • 也可从prev_right转移到当前右端点：curr_right = prev_right + (sorted_B[r] - sorted_B[r-1])，随后r -= 1，同样此路径总和更小，优先记录最大值
• 每次转移后更新prev_left和prev_right为当前状态的值。

4. 最终结果 #

遍历结束后，最大和为max(prev_left, prev_right)。

示例验证 #

以题目示例为例：

• A = [1,6,4,2]，生成op = [-1,1,1]
• B排序后为[2,4,5,9]
• 初始化prev_left=0，prev_right=0，l=0，r=3
• i=1（第二个元素），op[0]=-1：curr_left = 0 + (9-2)=7，l=1
• i=2（第三个元素），op[1]=1：curr_right=7+(5-2)=10，r=2；curr_left=7+(4-2)=9，l=2
• i=3（第四个元素），op[2]=1：curr_right=9+(5-4)=10
• 最终最大和为max(9,10)=10，与示例一致。

时间复杂度 #

• 排序B：O(n log n)
• 生成约束序列：O(n)
• DP遍历：O(n)
  总时间复杂度为O(n log n)，满足N=1e5的约束。

内容的提问来源于stack exchange，提问作者Puneet Sheokand