csr4

public class csr4 {

    /**
     *  csr4: given 2D array of integers (possibly negative) ,
     *  you start from cell (0,0)  and stop at cell (h-1,w-1)
     *  where h and w are height and width and each cell can't be visited more than 1 time.
     *  you add the integer in each cell you visit to your Current Sum ,
     *  find the maximum possible sum.
     */

    static int [][] map =  {{  2,  3, 40,  5, 2},
                            {  4, 54,  6,  8, 0},
                            {  8,  6,  5,  3, 0},
                            { 34, 65,  8, 66, 9},
                            { 44,  6,  7, 23, 1}};


    public static int solve(int i, int j) {

        if (i >= map.length || j >= map[0].length) {
            return -1;

        } else if (i == map.length && j == map[0].length) {
            return map[i][j];
        } else {
            return map[i][j] + Math.max(solve(i + 1, j),solve(i, j + 1));
        }
    }


    public static int solveDP(){
        int a[][] = new int[map.length][map[0].length];
        for (int i = a.length-1 ; i >= 0; i--) {
            for (int j = a[0].length-1 ; j >= 0; j--) {
                if (i==map.length-1 || j==map[0].length-1)
                    a[i][j] = map[i][j];
                else a[i][j] = map [i][j] + Math.max(a[i][j+1], a[i+1][j]);
            }
        }

        return a[0][0];
    }
    public static void main(String[] args) {

        int a = solve(0, 0);
        System.out.println("REC SOLUTION : " + a);
        System.out.println("DP  SOLUTION : "+solveDP());

    }

}