C ++程序中n个数组的升序元素的最大和

在这个问题中，我们得到大小为nXm的二维矩阵。我们的任务是创建一个程序，以从n个数组中找到递增顺序元素的最大和。

程序说明-在这里，我们需要通过从每一行中选取一个元素以使第i行中的元素小于第（i + 1）行中的元素的方式找到元素的最大和。等等。如果没有这样的总和，则返回-1表示没有结果。

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

输入项

mat[][] = {
   {4, 5, 1, 3, 6},
   {5, 9, 2, 7, 12},
   {13, 1, 3, 6, 8},
   {10, 5, 7, 2, 4}
}

输出结果

31

说明

Taking elements from the matrix to create max Sum:
6 + 7 + 8 + 10 = 31,
6 From array 1, the maximum value.
7 from array 2, choosing 12(maximum value) cannot provide a solution.
8 from array 3, choosing 13(maximum value) cannot provide a solution.
10 From array 4, the maximum value

解决方法

解决该问题的方法是从数组的最后一个数组中选择一个元素，然后向上选择比给定元素小的最大可能元素。

现在，使用此解决方案，当第i个数组（行）中的元素不小于第（i + 1）个数组（行）中的元素时，我们有一种情况。在这里，我们将返回-1。

对数组进行排序可以对我们解决方案的效率提供很好的帮助。就像我们按升序排序一样，最大元素将在索引m-1处，而下一个元素将较小。因此，容易找到满足条件的最大元素。

算法

初始化maxSum = 0，currMax

第1步-

Sort each array of the array of arrays (each will have elements in
increasing order).

第2步-

currMax = mat[n−1][m−1], the last element or the last row. Update
maxSum, maxSum = currMax.

第3步-

循环遍历矩阵rowise，i = n-2至0。

步骤3.1 -

Find the max element in mat[i][] which is smaller than
currMax at index j.

步骤3.2 -

if j < 0, i.e. no value found. Return −1.

步骤3.3 -

Update currMax. currMax = mat[i][j].

步骤3.4 -

Update maxSum, maxSum = currMax.

第4步-

Return maxSum.

示例

该程序说明了我们解决方案的工作原理，

#include <bits/stdc++.h>
#define M 5
using namespace std;
int calcMaxSumMat(int mat[][M], int n) {
   for (int i = 0; i < n; i++)
   sort(mat[i], mat[i] + M);
   int maxSum = mat[n − 1][M − 1];
   int currMax = mat[n − 1][M − 1];
   int j;
   for (int i = n − 2; i >= 0; i−−) {
      for (j = M − 1; j >= 0; j−−) {
         if (mat[i][j] < currMax) {
            currMax = mat[i][j];
            maxSum += currMax;
            break;
         }
      }
      if (j == −1)
      return 0;
   }
   return maxSum;
}
int main() {
   int mat[][M] = {
      {4, 5, 1, 3, 6},
      {5, 9, 2, 7, 12},
      {12, 1, 3, 6, 8},
      {10, 5, 7, 2, 4}
   };
   int n = sizeof(mat) / sizeof(mat[0]);
   cout<<"n个数组中升序元素的最大和为 "<<calcMaxSumMat(mat, n);
   return 0;
}

输出结果

n个数组中升序元素的最大和为 31