이 문제에서는 크기가 nXm인 2차원 행렬이 제공됩니다. 우리의 임무는 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+1번째 배열(행)에 있는 요소보다 작은 itharray(행)에 요소가 없는 경우가 하나 있습니다. 여기에서 -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<<"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