C++でm以下の長さの最大合計配列を検索します

この問題では、長さの異なるn個の配列が与えられます。私たちのタスクは、m以下の長さの最大合計配列を見つけることです。

合計を最大化し、結合されたすべてのサブ配列の長さをmに等しくするには、配列からサブ配列を見つける必要があります。

問題を理解するために例を見てみましょう

入力

n = 3, m = 4
arrOfArr[][] = {
   {5, 2, -1, 4, -3}
   {3, -2, 1, 6}
   {-2, 0, 5}
}

出力

20

説明

SubArrays are {5, 4}, {6}, {5},
length = 2 + 1 + 1 = 4
Sum = 5 + 4 + 6 + 5 = 20

ソリューションアプローチ

この問題は、動的計画法を使用して解決できます。 DP配列を作成し、0からmまで変化する長さkの累積配列合計を計算します。

DPアレイでは、2DDPの各アレイの0からmまでのすべての長さの最大アレイ合計を格納します。次に、配列の最後の行にある最大合計を返します。

ソリューションの動作を説明するプログラム

例

#include <bits/stdc++.h>
using namespace std;
#define N 5
int findMax(int a, int b){
   if(a > b)
      return a;
      return b;
}
int findMaxSumArray(int arr[][N], int M) {
   int DP[N][M];
   int sumArray[M];
   int sum[M];
   memset(DP, -1, sizeof(DP[0][0]) * N * M);
   sumArray[0] = 0;
   DP[0][0] = 0;
   for (int i = 1; i <= 5; i++) {
      int len = arr[i - 1][0];
      for (int j = 1; j <= len; j++) {
         sumArray[j] = arr[i - 1][j];
         sumArray[j] += sumArray[j - 1];
         sum[j] = -100;
      }
      for (int j = 1; j <= len && j <= 6; j++)
         for (int k = 1; k <= len; k++)
            if (j + k - 1 <= len)
               sum[j] = findMax(sum[j], sumArray[j + k - 1] - sumArray[k - 1]);
         for (int j = 0; j <= 6; j++)
            DP[i][j] = DP[i - 1][j];
         for (int j = 1; j <= 6; j++)
            for (int cur = 1; cur <= j && cur <= len; cur++)
               DP[i][j] = findMax(DP[i][j], DP[i - 1][j - cur] + sum[cur]);
   }
   int maxSum = 0;
   for (int i = 0; i <= 6; i++)
      maxSum = findMax(maxSum, DP[5][i]);
      return maxSum;
}
int main() {
   int arr[][N] = { { 3, 2, -1, 6 },
   { 2, 7, -1 },
   { 3, 2, 2, -4 } };
   int m = 4;
   cout<<"Maximum sum array of length less than or equal to "<<m<<" : "<<findMaxSumArray(arr, m);
}

出力

Maximum sum array of length less than or equal to 4 : 15