ในปัญหานี้ เราได้รับเมทริกซ์ 2 มิติขนาด M*N งานของเราคือสร้างโปรแกรมที่จะหาผลรวมพาธสูงสุดในเมทริกซ์
ในที่นี้ ผลรวมเส้นทางสูงสุดในเมทริกซ์ถูกกำหนดเป็นผลรวมขององค์ประกอบทั้งหมดสำหรับหนึ่งแถวถึงแถวสุดท้าย การเคลื่อนที่ที่อนุญาตสำหรับการเคลื่อนที่ในเส้นทางคือการเคลื่อนที่ลงและการเคลื่อนที่ในแนวทแยง จุดเริ่มต้นและจุดสิ้นสุดสามารถเป็นองค์ประกอบใดก็ได้ในแถวแรกและแถวสุดท้ายของเมทริกซ์ตามลำดับ
ลองมาดูตัวอย่างเพื่อทำความเข้าใจปัญหา
ป้อนข้อมูล −
matrix [][] = 3 5 9 1 7 2 4 8 6
ผลผลิต − 24
คำอธิบาย − เส้นทางสูงสุดจะเป็น 9 → 7 → 8
ในการแก้ปัญหา เราจะเริ่มจากด้านบนของอาร์เรย์และค้นหาองค์ประกอบที่ใหญ่ที่สุดของแถวแรก และจัดเก็บไว้ใน maxSum . จากนั้นข้ามเมทริกซ์และหาค่าสูงสุดที่เกิดขึ้นในเส้นทาง หากค่าใหม่มีการปรับปรุงมากขึ้น maxSum มิฉะนั้นอย่าอัปเดต และเมื่อข้ามเมทริกซ์ทั้งหมดและสร้างเส้นทางแล้ว ให้คืนค่า maxSum .
ตัวอย่าง
โปรแกรมหาผลรวมเส้นทางสูงสุดในเมทริกซ์ −
#include <iostream>
#define N 3
#define M 3
using namespace std;
int maxPathSum(int mat[][M]){
for (int i = 1; i < N; i++) {
for (int j = 0; j < M; j++) {
if (j > 0 && j < M - 1)
mat[i][j] += max(mat[i - 1][j], max(mat[i - 1][j - 1],mat[i - 1][j + 1]));
else if (j > 0)
mat[i][j] += max(mat[i - 1][j],
mat[i - 1][j - 1]);
else if (j < M - 1)
mat[i][j] += max(mat[i - 1][j],
mat[i - 1][j + 1]);
}
}
int maxSum = mat[N-1][0];
for (int j = 1; j < M; j++)
maxSum = max(mat[N-1][j], maxSum);
return maxSum;
}
int main(){
int matrix[N][M] = {
{3, 5, 9 },
{1, 7, 2},
{4, 8, 6}};
cout<<"The maximum path sum of matrix is : "<<maxPathSum(matrix);
return 0;
} ผลลัพธ์
The maximum path sum of matrix is : 24
