資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告