For any given matrix find the path from the start to the end which gives the maximum sum. Traverse only right or down. Example: starting index is 15 (left top) and ending index is 10 (bottom right) 15 25 30 45 25 60 70 75 10 O/P:15->45->70->75->10 sum is 215

Problem

For any given matrix find the path from the start to the end which gives the maximum sum. Traverse only right or down.
Example: starting index is 15 (left top) and ending index is 10 (bottom right)
15 25 30
45 25 60
70 75 10
O/P:15->45->70->75->10 sum is 215

Solution

#include<stdio.h>
int main()
{
    int row=0,col=0;
    scanf("%d %d",&row,&col);
    int arr[row][col];
    int i,j;
    for(i=0;i<row;i++)
    {
        for(j=0;j<col;j++)
        {
            scanf("%d",&arr[i][j]);
        }
    }
    for(i=0;i<row;i++)
    {
        for(j=0;j<col;j++)
        {
            printf("%d ",arr[i][j]);
        }
        printf("\n");
    }
    int sum=arr[0][0];
    int cr=0,cc=0;
    int prevrow=row-1;
    int prevcol=col-1;
    while(1)
    {
        
        int down=arr[cr+1][cc];
        int right=arr[cr][cc+1];
        if(cr+1>=row)
        {
            down=0;
        }
        if(cc+1>=col)
        {
            right=0;
        }
        if(down>right)
        {
            cr=cr+1;
            sum+=arr[cr][cc];
        }
        else if(right>down)
        {
            cc=cc+1;
            sum+=arr[cr][cc];
        }
        if((cr==prevrow)&&(cc==prevcol))
        {
            break;
        }
    }
    printf("%d",sum);
}

output:

15 25 30                                                                                                                                        
45 25 60                                                                                                                                        
70 75 10                                                                                                                                        
215  


Comments

Popular posts from this blog

C program to print the following Pattern

c++ program to print string along the diagonals of the matrix.