CareerCup

You can convert the grid into a directed graph. (Every vertex u will have an edge to its above/down/left/right vertex v, if the value at the vertex v is smaller than the value at vertex u. This will give you a DAG ( there can't be any cycle , think why?).

So, basically it turns out to be a problem of finding longest path in a DAG. Finding longest path in a normal graph is NP complete, however it can be done in linear time for a DAG.
Here's the algo:
- Get the topological sort of the graph
- start from the node at the end of the topological sort(it won't have any outgoing edge), say the node is w. so the length of longest path starting at w is zero.
- Now look at the second last node , and assign the length of longest path starting at this node (it will be 1 if it has a outgoing edge to the last one or else zero).
- similarly, keep doing this until you reach the first node, and at the end take the max of longest path starting at each node v.
So, the length of longest path starting at v is max(length of longest path starting at u +1), where u are all those nodes such that (v,u) is an edge in the graph.

DFS algorithm can be used to find the longest path here.

Now this is Complicated.

This is clearcut the graph problem. I think people may use Dijkstra's or Prims Algo to rescue .

However, the full fledged working code in interview time is doubtful.

Create a second array that records the longest possible path for each peak. Then work from the lowest peak to the highest peak and check whether going up in any of the four directions can imprive the longest path for the adjacent peaks. The highest number in the new array is the length of the longest path.

This solution requires an additional grid and an auxiliary array for sorting, which makes traversing the grid from the lowest to the highest peak easier.

Example code (in C, sorry):

#define MAX 20

struct Peak {
    int h;
    int x;
    int y;
};

int peak_cmp(const void *a, const void *b)
{
    const struct Peak *pa = a;
    const struct Peak *pb = b;
    
    return pb->h - pa->h;
}

int longest(int a[MAX][MAX], int width, int height)
{
    int l[MAX][MAX] = {{0}};
    struct Peak peak[MAX * MAX];
    int x, y, n;
    int max = 0;
    
    n = 0;
    for (x = 0; x < width; x++) {
        for (y = 0; y < height; y++) {
            struct Peak p = {a[y][x], x, y};
            peak[n++] = p;
        }
    }
    
    qsort(peak, n, sizeof(*peak), peak_cmp);
    
    while (n--) {
        int h = peak[n].h;
        
        x = peak[n].x;
        y = peak[n].y;
        
        l[y][x]++;
        if (l[y][x] > max) max = l[y][x];
        
        #define CHECK(C, X, Y)                              \
            if (C && a[Y][X] > h && l[Y][X] < l[y][x]) {    \
                l[Y][X] = l[y][x];                          \
            }
        
        CHECK(x, x - 1, y);
        CHECK(x + 1 < width, x + 1, y);
        CHECK(y, x, y - 1);
        CHECK(y + 1 < height, x, y + 1);
    }
    
    return max;
}

Create a Directed acyclic graph(you can't get cyclic graph).
a: {b,c,d,e}
Where a is connected to b, c, d and e.
Once you have this graph ready use this technique to find out the maximum distance and return it.
moodle.bracu.ac.bd/pluginfile.php/4784/mod_resource/content/1/longest-path-in-dag.pdf

Graph is fine but it could also be solved much easier using DP for the Longest Increasing Subsequence: en.wikipedia.org/wiki/Longest_increasing_subsequence

I guess my algorithm may save some time in solving
Algorithm:
1. Construct the graph with all peaks as nodes and there will be an edge between each adjacent node which is directed from higher to lower peak
2.Get the nodes which has inbound as '0' because that is the starting point that a longest path can start from.
3.Get the nodes which has outbound as '0' because that is the end point that a longest path can end.
4.Now we have only few nodes to consider.
5.Do dfs for all nodes with 0 inbound (of course each dfs will end in 0 outbound vertex).
6.Now the dfs with maximum length will be the solution

My solution will decrease the usage of dfs in the algorithm.

Can any one give me the idea to implemrnt this in java

Is there no starting and ending point? Looks like an all-pair longest path.

dynamic programming

You could convert it to a graph (where each cell is a vertex and its neighbors are only those cells whose value is smaller) and then use a modified Floyd-Warshall algorithm on it: modified, because it would look for max(longestPath(i, j, k), longestPath(i, k+1, k) + longestPath(k+1, j, k)) instead of min(shortestPath(i, j, k), shortestPath(i, k+1, k) + shortestPath(k+1, j, k)).

The comlexity would be O((MxN)^3) where M and N are grid dimensions. I can't think of a more optimized solution at the moment.

the input can be converted into a tree with each node having left right down and up children nodes and then do depth first algorithm