DP_N*N 이동경로 최대값을 구하라(음수존재)

문제

• n*n 2차원 격자에 숫자가 써있음(음수 존재)
• 오른쪽,아래로만 이동가능
• 0,0 에서 n-1,n-1까지도 이동경로의 최대값을 구하여라

public class Main {

    static int max = 0;
    static int [][] dwMove;
    static int N,M;


    public static void main(String[] args) {
        int[][] arr = {{-5, 10, 50},
                         {-30, 2, 80},
                         {-60, 20, 9}};
        N = arr.length;
        M = arr.length;


        max = -999999999;
        dwMove = new int[N][M];


        dwMove[0][0] = arr[0][0];
        for(int i = 0; i < N ; i++){
            for(int j = 0; j < N ; j++){
                int arrnum =  arr[i][j];
                if(i==0){ 
                    //격자 맨 윗줄
                    if(j==0) continue;
                   
                    dwMove[i][j] = dwMove[i][j-1] + arrnum;
                }else if(j==0){ 
                		//격자 맨 왼쪽줄
                        dwMove[i][j] = dwMove[i-1][j] + arrnum;
                }else{

                        dwMove[i][j] = Math.max(dwMove[i - 1][j] + arrnum, dwMove[i][j - 1] + arrnum);
                }

            }
        }


        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                max = Math.max(dwMove[i][j] , max);
            }
        }

        System.out.println(max);


    }

}