微客导航 » 文章资讯 » 在C ++中查找长度小于或等于m的最大和数组!

在C ++中查找长度小于或等于m的最大和数组!

2023-06-16 13:36:04 175

在这个问题中，我们给出了n个不同长度的数组。我们的任务是找到长度小于或等于m的最大和数组。

我们需要从数组中找到子数组以最大化总和并使所有子数组的长度组合等于m。

让我们举个例子来理解这个问题，

输入

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

输出结果

解释

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 
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<<"长度小于或等于的最大和数组 "<输出结果长度小于或等于的最大和数组 4 : 15

返回顶部
3162201930
czq8825@qq.com

在C ++中查找长度小于或等于m的最大和数组!

输入

解释

解决方法

示例

热门推荐

随机推荐