algorithm - Longest increasing subsequence in a 2D matrix. -

i solving programming challenge find length of longest increasing subsequence in 2d nxn matrix. both row , columns must increase in each element of sequence (no need consecutive) . solved dynamic programming approach o(n^4) , inefficient. however, there many solutions in o(n^3). 1 such solution is:

   scanf("%d", &n);     for(i = 1; <= n; i++) {         for(j = 1; j <= n; j++) {             scanf("%d", &l[i][j]);         }     }     answer = 0;       memset(maxlength,0,sizeof(maxlength));     (i=1;i<=n;i++)      {         maxlength[1][i] = 1;         maxlength[i][1] = 1;     }      //     (i=2;i<=n;i++)     {          memset(minvalue,0,sizeof(minvalue));         curlen = 1;         minvalue[1] = l[i-1][1];           (j=2;j<=n;j++)           {             (p=1;p<i;p++)             {                 tmplen = maxlength[p][j-1];                 if (minvalue[tmplen] == 0)                 {                     minvalue[tmplen] = l[p][j-1];                      curlen = tmplen;                 }                 else if (minvalue[tmplen]>l[p][j-1])                 {                     minvalue[tmplen] = l[p][j-1];                 }             }               max = 1;             (p=curlen;p>0;p--)             {                 if (l[i][j]>=minvalue[p])                 {                     max = p+1;                     break;                 }             }              maxlength[i][j] = max;             answer = answer>max?answer:max;         }     }      // print answer standard output(screen).     printf("%d\n", answer); 

can explain how works or other o(n^3) approach ? can't follow @ :(.

it's not difficult solve in o(n³) time. didn't read source code, however, don't know if following did, here idea of how done.

the trick in update procedure. guess did following.

say considering element in orange rectangle. previous step has originate blue rectangle (which solved). yields correct answer, it's easy see yield θ(n⁴) result, can make both orange , blue rectangles θ(n²), , need consider pairs between them. (it's easy formalize this.)

instead, start solving first row , first column. in fact, in each iteration, take next unsolved row , column, , solve them solved parts.

here's trick (which i'll leave you). if store enough information in cells (or in auxiliary data structures, doesn't matter), each element in orange column you're considering, need @ column left of (ditto orange row - need @ elements in row above it).

so there o(n) outer iterations (in each 1 consider row , column). each such row/column has o(n) elements, , each left/up row/column has o(n) elements two. multiplication gives target complexity.