数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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
解释
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 次浏览
广告