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
  • 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];
    
    }
    


  • 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!!

  • 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.

[Insert Code]