C++程序中n个数组递增序列元素的最大和

在这个问题中，我们得到一个n x m大小的二维矩阵。我们的任务是创建一个程序来查找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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

解释

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 −

逐行遍历矩阵，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<<"The maximum sum of increasing order elements from n arrays is "<<calcMaxSumMat(mat, n);
   return 0;
}

输出

The maximum sum of increasing order elements from n arrays is 31

更新于：2020年12月9日

106 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告