Given a M*N matrix A in which all the elements in a row and all the elements in a column are strictly increasing. Find a path from the smallest element (ie A[0][0]) to the largest element (ie A[M-1][N-1]) such that the sum of the elements in the path is maximum. Time Complexity O(m+n). Use efficient space
Click for Solution

  • Warning: Illegal string offset 'name' in /home/prepdo6/gpl4you/discussquessub.php on line 681
    A 
    /* */

main()
{
	int i,j=0,A[3][3]={1,2,3,3,5,8,4,7,18},pc;
	clrscr();
	pc=A[0][0];
	for(i=0;i<2;)
		for(j=0;j<2;){
			if(A[i+1][j] > A[i][j+1])
			{
				pc+=A[++i][j];
				if(i==2)
				{
					endx(i,j,&pc,&A,0);
					j=2;
					break;
				}
			}
			else
			{
				pc+=A[i][++j];
				if(j==2)
				{
					endx(i,j,&pc,&A,1);
					i=2;
					break;
				}
			}
		}
	printf("PC=%d",pc);
}

endx(int i,int j, int *PC, int P[3][3], int c)
{
	if(c==0)
		while(j<2)
			*PC+=P[i][++j];
	else
		while(i<2)
			*PC+=P[++i][j];

}



    Smiley

  • Warning: Illegal string offset 'name' in /home/prepdo6/gpl4you/discussquessub.php on line 681
    A Yes the solution given is wrong,

    it can't be done using greedy solution solution also, i.e. if we try to compare both the values in the row as well as column and move along the path!!


    A better solution needed!!


    Smiley

  • Warning: Illegal string offset 'name' in /home/prepdo6/gpl4you/discussquessub.php on line 681
    A your solution is wrong..
    pls check with this one..
    1 3 7
    2 4 8
    3 28 29..

    solution will be 1-->3-->4-->28-->29.


    Smiley
[Insert Code]