Question

MATLAB ONLY:

Write a user defined method MaxPath()

Find the maximum path sum in matrix. The maximum path is sum of all section from first to last
row where you can move only down or at a angle to left or right. You can start from any section
in first row of given matrix of P*Q.
Input: mat [] [] = 10 10 2 0 20 4
1 0 0 30 2 5
0 10 4 0 2 0
1 0 2 20 0 4
Output: 74
The maximum sum path is 20-30-4-20.
Input: mat [] [] = 1

Answer 1

When you directly copy paste the code in the MATLAB Editor you will get error because the tab spaces will be converted into blank spaces. To resolve the error replace the blank spaces with appropriate tab spaces. You can use the screenshot of the code for number of tab spaces required.

X=[10 10 2 0 20 4;
1 0 0 30 2 5;
0 10 4 0 2 0;
1 0 2 20 0 4];
MaxPath(X)
function sum = MaxPath(mat)
[p,q] = size(mat);
res = -1;
for i = 1:q
res = max([res mat(1,i)]);
end
for i = 2:p
res = -1;
for j = 1:q
if ((j>1) && (j<q))
mat(i,j) = mat(i,j) + max([mat(i-1,j) max([mat(i-1,j-1) mat(i-1,j+1)])]);
elseif (j>1)
mat(i,j) = mat(i,j) + max([mat(i-1,j) mat(i-1,j-1)]);
elseif (j<q)
mat(i,j) = mat(i,j) + max([mat(i-1,j) mat(i-1,j+1)]);
end
res = max(mat(i,j),res);
end
end
sum = res;
end

X=[10 10 2 0 20 4; % Test Matrix for verification
1 0 0 30 2 5;
0 10 4 0 2 0;
1 0 2 20 0 4];
MaxPath(X) % Calling the function MaxPath for verification
function sum = MaxPath(mat) % Start of function MaxPath()
[p,q] = size(mat); % To find matrix size
res = -1; % To find max value in first row
for i = 1:q
res = max([res mat(1,i)]);
end
for i = 2:p
res = -1;
for j = 1:q % When all paths are possible
if ((j>1) && (j<q))
mat(i,j) = mat(i,j) + max([mat(i-1,j) max([mat(i-1,j-1) mat(i-1,j+1)])]);
elseif (j>1) % When diagonal right is not possible
mat(i,j) = mat(i,j) + max([mat(i-1,j) mat(i-1,j-1)]);
elseif (j<q) % When diagonal left is not possible
mat(i,j) = mat(i,j) + max([mat(i-1,j) mat(i-1,j+1)]);
end
res = max(mat(i,j),res); % Store max path sum
end
end
sum = res;
end % End of function MaxPath()

The below output is obtained for the given test data.