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