LongestPath.java

package com.ldt.test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TestMain2 {
    public static void main(String[] args) {
        int[][] datas = new int[][]{
                {3, 2, 1, 100},
                {5, 2, 1, 1},
                {4, 3, 1, 1}};
        System.out.println(findLongestPath(datas));
    }

    private static int findLongestPath(int[][] datas){
        int numRows = datas.length;
        int numCols = datas[0].length;
        int result = Integer.MIN_VALUE;

        List<Integer> lengths = new ArrayList<>();
        // step 1 find position in map
        Map<Integer, List<Position>> mapPosition = new HashMap<>();
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                Integer data = datas[i][j];
                if(!lengths.contains(data)){
                    lengths.add(data);
                }
                Position position = new Position(i, j);
                List<Position> positions;
                if(!mapPosition.containsKey(data)){
                    positions = new ArrayList<>();
                }else{
                    positions = mapPosition.get(data);
                }
                positions.add(position);
                mapPosition.put(data, positions);
            }
        }
        int[][] results = new int[numRows][numCols];

        // sap xep cac do cao theo chieu tang dan
        lengths.sort(Integer::compareTo);
        for (int i = 1; i < lengths.size(); i++) {
            List<Position> positionByValue = mapPosition.get(lengths.get(i));

            for (int j = 0; j < positionByValue.size(); j++) {
                Position position = positionByValue.get(j);
                int value = datas[position.getX()][position.getY()];
                // check top
                int nextValue = 0;
                if(position.getX()>0){
                    if(datas[position.getX()-1][position.getY()]<value){
                        nextValue = results[position.getX()-1][position.getY()] + 1;
                    }
                }

                // check bottom
                if(position.getX()<numRows-1){
                    if(datas[position.getX()+1][position.getY()]<value){
                        int temp = results[position.getX() + 1][position.getY()] + 1;
                        nextValue = nextValue>temp?nextValue:temp;
                    }
                }

                // check left
                if(position.getY()>0){
                    if(datas[position.getX()][position.getY()-1]<value){
                        int temp = results[position.getX()][position.getY()-1] +1;
                        nextValue = nextValue>temp?nextValue:temp;
                    }
                }

                // check right
                if(position.getY()<numCols-1){
                    if(datas[position.getX()][position.getY()+1]<value){
                        int temp = results[position.getX()][position.getY()+1] + 1;
                        nextValue = nextValue>temp?nextValue:temp;
                    }
                }

                results[position.getX()][position.getY()] = nextValue;
            }
        }

        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) {
                result = result>results[i][j]?result:results[i][j];
            }
        }
        return result;
    }




}

package com.ldt.test;

public class Position {
private int x;
private int y;

public Position(int i, int j) {
    this.x = i;
    this.y = j;
}

public int getX() {
    return x;
}

public void setX(int x) {
    this.x = x;
}

public int getY() {
    return y;
}

public void setY(int y) {
    this.y = y;
}

}