arrays - 来自两个不同数组的最大切片和

Question

Original Problem: Problem 1 (INOI 2015)

有两个数组A[1..N]和 B[1..N]

一个操作SSum在它们上定义为

• SSum[i,j] = A[i] + A[j] + B[t (where t = i+1, i+2, ..., j-1)]什么时候i < j
• SSum[i,j] = A[i] + A[j] + B[t (where t = 1, 2, ..., j-1, i+1, i+2, ..., N)]什么时候i > j
• SSum[i,i] = A[i]

挑战在于找到 SSum 的最大可能值。

我有一个基于计算 B 的前缀和的 O(n^2) 解决方案

#include <iostream>
#include <utility>

int main(){
  int N;
  std::cin >> N;

  int *a = new int[N+1];
  long long int *bPrefixSums = new long long int[N+1];

  for (int iii=1; iii<=N; iii++) //1-based arrays to prevent confusion
    std::cin >> a[iii];
  bPrefixSums[0] = 0;
  for (int b,iii=1; iii<=N; iii++){
    std::cin >> b;
    bPrefixSums[iii] = bPrefixSums[iii-1] + b;
  }

  long long int SSum, SSumMax=-(1<<10);

  for (int i=1; i <= N; i++)
    for (int j=1; j <= N; j++){
      if (i<j)
        SSum = a[i] + a[j] + (bPrefixSums[j-1] - bPrefixSums[i]);
      else if (i==j)
        SSum = a[i];
      else
        SSum = a[i] + a[j] + ((bPrefixSums[N] - bPrefixSums[i]) + bPrefixSums[j-1]);
      SSumMax = std::max(SSum, SSumMax);
    }

  std::cout << SSumMax;

  return 0;
}

对于 10^6 左右的较大 N 值，程序无法在 3 秒内完成任务。

Answer 1

由于我没有获得足够的代表来添加评论，所以我将在此答案中只写下想法。

这个问题真的很好，我实际上是被这个启发了link .感谢@superty。

我们可以把这个问题分开来考虑，换句话说，分为三种情况:i == j , i < j , i > j .而我们只需要找到最大的结果。

考虑 i == j : 最大的结果应该是a[i]，在O(n)的时间复杂度内很容易找到答案。

考虑 i < j :这与经典的最大和问题非常相似，并且对于每个 j我们只需要找到 i在左边，设法使结果最大。

首先考虑经典问题，如果我们被要求获得数组 a 的最大部分和，我们计算 a 的前缀和以获得 O(n) 复杂度。现在在这个问题上，几乎是一样的。

你可以看到这里(i < j)，我们有SSum[i,j] = A[i] + A[j] + B[t (where t = i+1, i+2, ..., j-1)] = (B[1] + B[2] + ... + B[j - 1] + A[j]) - (B[1] + B[2] + ... B[i] - A[i]) , 当 j 时第一项保持不变当 i 时，第二项保持不变。保持不变。所以现在的解决方案很清楚，你得到两个“前缀和”并找到最小的 prefix_sum_2[i]对于每个 prefix_sum_1[j] .

考虑 i > j : 与此非常相似 discussion在 SO 上(但这个讨论没有多大帮助)。

类似地，我们得到SSum[i,j] = A[i] + A[j] + B[t (where t = 1, 2, ..., j-1, i+1, i+2, ..., N)] = (B[1] + B[2] + ... + B[j - 1] + A[j]) + (A[i] + B[i + 1] + ... + B[n - 1] + B[n]) .现在你需要得到数组的前缀和和后缀和(我们需要 prefix_sum[i] = a[i] + prefix_sum[i - 1] - a[i - 1] 和后缀类似)，并得到另外两个数组，比如 ans_left[i]作为the maximum value of the first term for all j <= i和 ans_right[j]作为the maximum value of the second term for i >= j , 所以这个条件下的答案是所有 (ans_left[i] + ans_right[i + 1]) 中的最大值

最后，原始问题所需的最大结果是这三个子案例答案的最大值。

很明显总的复杂度是O(n)。