class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if(len == 1)return nums[0];
        int res = nums[0];
        int dp[] = new int[len];
        dp[0] = nums[0];
        for(int i = 1;i < len;i++){
            dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
            res = Math.max(dp[i],res);
        }
        return res;
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];
        for(int i = 0;i < m;i++){
            dp[i][0] = 1;
        }
        for(int i = 0;i < n;i++){
            dp[0][i] = 1;
        }
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int dp[][] = new int[m][n];
        for(int i = 0;i < m;i++){
            if(i == 0){
                dp[i][0] = grid[0][0];
                continue;
            }
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int i = 0;i < n;i++){
            if(i == 0) continue;
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for(int i = 1;i < m;i++){
            for(int j = 1;j < n;j++){
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}