Trong bài toán này, chúng ta được cung cấp một ma trận 2-D có kích thước nXm. Nhiệm vụ của chúng tôi là tạo ra chương trình để tìm tổng số tối đa của các phần tử có thứ tự tăng dần từ n mảng.
Mô tả chương trình - Ở đây, chúng ta cần tìm tổng lớn nhất của các phần tử bằng cách lấy một phần tử từ mỗi hàng sao cho phần tử từ hàng thứ i nhỏ hơn phần tử từ hàng thứ (i + 1). Và như thế. Nếu không thể có tổng như vậy, trả về −1 biểu thị là không thể có kết quả.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
mat[][] = {
{4, 5, 1, 3, 6},
{5, 9, 2, 7, 12},
{13, 1, 3, 6, 8},
{10, 5, 7, 2, 4}
} Đầu ra
31
Giải thích
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
Phương pháp tiếp cận giải pháp
Giải pháp cho vấn đề là chọn một phần tử từ mảng cuối cùng của mảng mảng và sau đó chọn phần tử lớn nhất có thể nhỏ hơn phần tử đã cho.
Bây giờ, sử dụng giải pháp này, chúng ta gặp một trường hợp khi không có phần tử nào trong itharray (hàng) nhỏ hơn phần tử ở mảng (hàng) thứ (i + 1). Ở đây, chúng tôi sẽ trả về −1.
Sắp xếp mảng có thể là một trợ giúp tốt cho hiệu quả của giải pháp của chúng tôi. Như thể sắp xếp theo thứ tự tăng dần, phần tử lớn nhất sẽ ở chỉ số m − 1, và phần tử tiếp theo sẽ nhỏ hơn. Do đó, việc tìm phần tử lớn nhất thỏa mãn điều kiện thật dễ dàng.
Thuật toán
Khởi tạo maxSum =0, currMax
Bước 1 -
Sort each array of the array of arrays (each will have elements in increasing order).
Bước 2 -
currMax = mat[n−1][m−1], the last element or the last row. Update maxSum, maxSum = currMax.
Bước 3 -
Lặp lại ma trận theo chiều xoay vòng, i =n − 2 đến 0.
Bước 3.1 -
Find the max element in mat[i][] which is smaller than currMax at index j.
Bước 3.2 -
if j < 0, i.e. no value found. Return −1.
Bước 3.3 -
Update currMax. currMax = mat[i][j].
Bước 3,4 -
Update maxSum, maxSum = currMax.
Bước 4 -
Return maxSum.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
#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;
} Đầu ra
The maximum sum of increasing order elements from n arrays is 31