C++ 中两个不重叠子数组的最大和


假设我们有一个整数数组 A;我们需要找到两个不重叠子数组元素的最大和。这两个子数组的长度分别为 L 和 M。

更准确地说,我们需要找到最大的 V,其中

V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) 并且满足以下条件之一:

  • 0 <= i < i + L − 1 < j < j + M − 1 < A 的大小,或者

  • 0 <= j < j + M − 1 < i < i + L − 1 < A 的大小。

为了解决这个问题,我们将遵循以下步骤:

  • n := A 的大小

  • 定义一个大小为 n 的数组 leftL,定义一个大小为 n 的数组 leftM

  • 定义一个大小为 n 的数组 rightL,定义一个大小为 n 的数组 rightM

  • ret := 0,temp := 0

  • 初始化 i := 0,当 i < L 时,将 i 增加 1:

    • temp = temp + A[i]

  • 初始化 i := L,j := 0,当 i < n 时,将 i 增加 1,将 j 增加 1:

    • leftL[i − 1] := temp 和 x 的最大值,其中 x 为 0(如果 i − 2 < 0),否则 x = leftL[i − 2]

    • temp = temp + A[i]

    • temp = temp − A[j]

  • leftL[n − 1] := temp 和 x 的最大值,其中 x 为 0(如果 n − 2 < 0),否则 x := leftL[n − 2]

  • temp := 0

  • 初始化 i := 0,当 i < M 时,将 i 增加 1:

    • temp = temp + A[i]

  • 初始化 i := M,j := 0,当 i < n 时,将 i 增加 1,将 j 增加 1:

    • temp = temp + A[i]

    • temp = temp - A[j]

  • leftM[n − 1] := temp 和 x 的最大值,其中 x := 0(如果 n - 2 < 0),否则 x := leftM[n − 2]

  • temp := 0

  • 初始化 i := n − 1,当 i > n − 1 − L 时,将 i 减少 1:

    • temp = temp + A[i]

  • 初始化 i := n − 1 − L,j := n − 1,当 i >= 0 时,将 i 减少 1,将 j 减少 1:

    • rightL[i + 1] := temp 和 x 的最大值,其中 x 为 0(如果 i + 2 >= n),否则 x = rightL[i + 2]

    • temp = temp + A[i]

    • temp = temp − A[j]

  • rightL[0] := temp 和 rightL[1] 的最大值

  • temp := 0

  • 初始化 i := n − 1,当 i > n − 1 − M 时,将 i 减少 1:

    • temp = temp + A[i]

  • 初始化 i := n − 1 − M,j := n − 1,当 i >= 0 时,将 i 减少 1,将 j 减少 1:

    • rightM[i + 1] := temp 和 x 的最大值,其中 x 为 0(如果 i + 2 >= n),否则 x := rightM[i + 2]

    • temp = temp + A[i]

    • temp = temp − A[j]

  • rightM[0] := temp 和 rightM[1] 的最大值

  • 初始化 i := L − 1,当 i <= n − 1 − M 时,将 i 增加 1:

    • ret := ret 和 leftL[i] + rightM[i + 1] 的最大值

  • 初始化 i := M − 1,当 i <= n − 1 − L 时,将 i 增加 1:

    • ret := ret 和 leftM[i] + rightL[i + 1] 的最大值

  • 返回 ret

让我们看一下下面的实现,以便更好地理解:

示例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxSumTwoNoOverlap(vector<int>& A, int L, int M) {
      int n = A.size();
      vector <int> leftL(n);
      vector <int> leftM(n);
      vector <int> rightL(n);
      vector <int> rightM(n);
      int ret = 0;
      int temp = 0;
      for(int i = 0; i < L; i++){
         temp += A[i];
      }
      for(int i = L, j = 0; i < n; i++, j++){
         leftL[i − 1] = max(temp, i − 2 < 0 ? 0 : leftL[i − 2]);
         temp += A[i];
         temp −= A[j];
      }
      leftL[n − 1] = max(temp, n − 2 < 0 ? 0 : leftL[n − 2]);
      temp = 0;
      for(int i = 0; i < M; i++){
         temp += A[i];
      }
      for(int i = M, j = 0; i < n; i++, j++){
         leftM[i − 1] = max(temp, i − 2 < 0 ? 0 : leftM[i − 2]);
         temp += A[i];
         temp −= A[j];
      }
      leftM[n − 1] = max(temp, n − 2 < 0 ? 0 : leftM[n − 2]);
      //out(leftM);
      temp = 0;
      for(int i = n − 1; i > n − 1 − L; i−−){
         temp += A[i];
      }
      for(int i = n − 1 − L, j = n − 1; i >= 0 ; i−−, j−− ){
         rightL[i + 1] = max(temp, (i + 2 >= n ? 0 : rightL[i + 2]));
         temp += A[i];
         temp −= A[j];
      }
      rightL[0] = max(temp, rightL[1]);
      temp = 0;
      for(int i = n − 1; i > n − 1 − M; i−−){
         temp += A[i];
      }
      for(int i = n − 1 − M, j = n − 1; i >= 0 ; i−−, j−− ){
         rightM[i + 1] = max(temp, (i + 2 >= n ? 0 : rightM[i + 2]));
         temp += A[i];
         temp −= A[j];
      }
      rightM[0] = max(temp, rightM[1]);
      for(int i = L − 1; i <= n − 1 − M; i++){
         ret = max(ret, leftL[i] + rightM[i + 1]);
      }
      for(int i = M − 1; i <= n − 1 − L; i++){
         ret = max(ret, leftM[i] + rightL[i + 1]);
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v1 = {0,6,5,2,3,5,1,9,4};
   cout << (ob.maxSumTwoNoOverlap(v1, 1, 2));
}

输入

[0,6,5,2,3,5,1,9,4]
1
2

输出

20

更新于: 2020-11-13

182 次浏览

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告