数组最大反转和问题：如何将O(n²)时间复杂度优化至线性？

我们可以通过数学推导拆分问题，把枚举所有i和j的O(n²)操作，拆解为两个独立的O(n)子问题求解。

先推导总和的数学表达式 #

设原数组总和为total，定义：

• prefix[i]：数组前i+1个元素（0..i）的和
• suffix[j]：数组从j到末尾（j..n-1）的和
• sub_sum(j,i)：数组从j到i（j≤i）的子数组和

根据i和j的大小关系，分两种情况分析执行两次操作后的总和：

情况1：i < j

此时前缀翻转（0..i）和后缀翻转（j..n-1）的区域没有重叠：

• 0..i的元素被翻转一次，总和减少2*prefix[i]
• j..n-1的元素被翻转一次，总和再减少2*suffix[j]
  最终总和为：total - 2*(prefix[i] + suffix[j])

要最大化这个值，等价于最小化prefix[i] + suffix[j]（i<j）。我们可以预处理一个min_prefix数组，其中min_prefix[k]表示prefix[0]到prefix[k]的最小值。然后遍历每个j，取min_prefix[j-1] + suffix[j]的最小值即可，这一步是O(n)。

情况2：i >= j

此时前缀翻转和后缀翻转的区域有重叠，重叠部分（j..i）被翻转两次，相当于没变化；只有0..j-1和i+1..n-1被翻转一次：

• 这两部分的总和是total - sub_sum(j,i)，总和减少2*(total - sub_sum(j,i))
  最终总和为：2*sub_sum(j,i) - total

要最大化这个值，等价于最大化子数组和sub_sum(j,i)，直接用Kadane算法就能在O(n)时间内求出数组的最大子数组和。

最终步骤 #

1. 计算原数组总和total，预处理prefix、suffix数组
2. 预处理min_prefix数组，求解情况1的最小prefix[i]+suffix[j]，得到情况1的最大总和
3. 用Kadane算法求解情况2的最大子数组和，得到情况2的最大总和
4. 取两种情况的最大值，就是执行两次操作后的最大数组总和

整个过程只需要遍历数组常数次，时间复杂度为O(n)。

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