Tổng đường dẫn tối đa trong ma trận trong C ++

Trong bài toán này, chúng ta được cung cấp một ma trận 2D có kích thước M * N. Nhiệm vụ của chúng ta là tạo một chương trình tìm tổng đường dẫn tối đa trong ma trận.

Ở đây, tổng đường dẫn tối đa trong ma trận được định nghĩa là tổng của tất cả các phần tử cho một hàng đến hàng cuối cùng. Các bước di chuyển được phép để đi qua con đường là di chuyển xuống dưới và di chuyển theo đường chéo. Điểm đầu và điểm cuối tương ứng có thể là bất kỳ phần tử nào của hàng đầu tiên và cuối cùng của ma trận.

Hãy lấy một ví dụ để hiểu vấn đề

Đầu vào -

matrix [][] =
   3 5 9
   1 7 2
   4 8 6

Đầu ra - 24

Giải thích - Đường dẫn tối đa sẽ là 9 → 7 → 8.

Để giải quyết vấn đề, chúng ta sẽ bắt đầu từ đầu mảng và tìm phần tử lớn nhất của hàng đầu tiên, và lưu trữ vào maxSum . Sau đó, duyệt qua ma trận và tìm các giá trị lớn nhất xuất hiện trong đường dẫn. Nếu các giá trị mới lớn hơn, hãy cập nhật maxSum nếu không thì đừng cập nhật. Và khi toàn bộ ma trận được duyệt và đường dẫn được tạo sẽ trả về giá trị maxSum .

Ví dụ

Chương trình tìm tổng đường dẫn tối đa trong ma trận -

#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;
}

Đầu ra

The maximum path sum of matrix is : 24