ในปัญหานี้ เราได้รับเมทริกซ์ 2 มิติขนาด nXm งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวมสูงสุดของการเพิ่มองค์ประกอบลำดับจาก n อาร์เรย์
คำอธิบายโปรแกรม − ในที่นี้ เราจำเป็นต้องหาผลรวมสูงสุดขององค์ประกอบโดยนำองค์ประกอบหนึ่งรายการจากแต่ละแถวในลักษณะที่องค์ประกอบจากแถวที่ ith มีค่าน้อยกว่าองค์ประกอบจากแถวที่ (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
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาคือโดยการเลือกองค์ประกอบจากอาร์เรย์สุดท้ายของอาร์เรย์ของอาร์เรย์ แล้วเลือกองค์ประกอบที่ใหญ่ที่สุดเท่าที่จะเป็นไปได้ซึ่งมีขนาดเล็กกว่าองค์ประกอบที่กำหนด
เมื่อใช้วิธีแก้ปัญหานี้ เรามีกรณีหนึ่งเมื่อไม่มีองค์ประกอบใน itharray (แถว) ซึ่งน้อยกว่าองค์ประกอบที่อาร์เรย์ (i+1)th (แถว) ที่นี่เราจะกลับมา -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
