Mock Interview: Google

674. Longest Continuous Increasing Subsequence

class Solution {
    public int findLengthOfLCIS(int[] nums) {

        int seq = 1;
        int cur = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i-1]) {
                cur++;
            } else {
                seq = Math.max(seq, cur);
                cur = 1;
            }
        }
        
        seq = Math.max(seq, cur);
        
        return seq; 
    }
}

Runtime: 1 ms, faster than 98.79% of Java online submissions for Longest Continuous Increasing Subsequence.
Memory Usage: 39.8 MB, less than 38.19% of Java online submissions for Longest Continuous Increasing Subsequence.

전거랑 비교해서 커지면 1씩 올려주고
총을 계속 업데이트 해줬읍니다

1219. Path with Maximum Gold

class Solution {
    private int[][] g; 
    public int getMaximumGold(int[][] grid) {
        int gold = 0;
        this.g = grid.clone();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] != 0) {
                    int goldFromHere = maxGold(i, j, 0, 4);
                    gold = Math.max(gold, goldFromHere);
                }
            }
        }
        
        return gold + 1;
    }
    
    //need to mark where i've been
    //0: top 1: bottom 2: left 3: right
    private int maxGold(int y, int x, int total, int dir) {
        if (g[y][x] == 0) {
            return total;
        }
        
        int top, bottom, left, right = 0;
        int cur = g[y][x];
        if (y > 0 && dir != 0) {
            top = g[y-1][x];
            return maxGold(y-1, x, total + cur, 1);
        }
        
        if (y < g.length - 1 && dir != 1) {
            bottom = g[y+1][x];
            return maxGold(y+1, x, total + cur, 0);
        }
        
        if (x > 0 && dir != 2) {
            left = g[y][x-1];
            return maxGold(y, x-1, total + cur, 3);
        }
        
        if (x < g[0].length - 1 && dir != 3) {
            right = g[y][x+1];
            return maxGold(y, x+1, total + cur, 2);
        }
        
        return 0;
        
    }
}

재귀로 사방을 다 뒤지면서 업데이트 해줬읍니다
근데 계속 틀려서..
전체 값 대신 커지는 값만 더해줬읍니다

class Solution {
    private int[][] g; 
    public int getMaximumGold(int[][] grid) {
        int gold = 0;
        this.g = grid.clone();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                int goldFromHere = maxGold(i, j);
                gold = Math.max(gold, goldFromHere);
                
            }
        }
        
        return gold;
    }
    
    //need to mark where i've been
    //0: top 1: bottom 2: left 3: right
    private int maxGold(int y, int x) {
        if (g[y][x] == 0) {
            return 0;
        }
        
        int top, bottom, left, right = 0;
        int cur = g[y][x];
        g[y][x] = 0; 
        int total = 0;
        
        if (y > 0) {
            total = Math.max(total, maxGold(y-1, x));
        }
        
        if (y < g.length - 1) {
            total = Math.max(total, maxGold(y+1, x));
        }
        
        if (x > 0) {
            total = Math.max(total, maxGold(y, x-1));
        }
        
        if (x < g[0].length - 1) {
            total = Math.max(total, maxGold(y, x+1));
        }
        
        return cur + total;
    }
}

근데도 안되네요..
나오는 값이 전거랑 똑같은거 보니 돌아가는 방식도 같은가봐요

class Solution {
    public int getMaximumGold(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int maxGold = 0;
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                maxGold = Math.max(maxGold, findMaxGold(grid, m, n, r, c));
        return maxGold;
    }
    int[] DIR = new int[]{0, 1, 0, -1, 0};
    int findMaxGold(int[][] grid, int m, int n, int r, int c) {
        if (r < 0 || r == m || c < 0 || c == n || grid[r][c] == 0) return 0;
        int origin = grid[r][c];
        grid[r][c] = 0; // mark as visited
        int maxGold = 0;
        for (int i = 0; i < 4; i++)
            maxGold = Math.max(maxGold, findMaxGold(grid, m, n, DIR[i] + r, DIR[i+1] + c));
        grid[r][c] = origin; // backtrack
        return maxGold + origin;
    }
}

Runtime: 21 ms, faster than 52.37% of Java online submissions for Path with Maximum Gold.
Memory Usage: 36.1 MB, less than 93.57% of Java online submissions for Path with Maximum Gold.

class Solution {
    public int getMaximumGold(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int maxGold = 0;
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                maxGold = Math.max(maxGold, findMaxGold(grid, m, n, r, c));
        return maxGold;
    }
    
    int[] DIR = new int[]{0, 1, 0, -1, 0};
    
    int findMaxGold(int[][] grid, int m, int n, int r, int c) {
        if (r < 0 || r == m || c < 0 || c == n || grid[r][c] == 0) return 0;
        int origin = grid[r][c];
        grid[r][c] = 0; // mark as visited
        int maxGold = 0;
    
        maxGold = Math.max(maxGold, findMaxGold(grid, m, n, r + 1, c));
        maxGold = Math.max(maxGold, findMaxGold(grid, m, n, r, c + 1));
        maxGold = Math.max(maxGold, findMaxGold(grid, m, n, r - 1, c));
        maxGold = Math.max(maxGold, findMaxGold(grid, m, n, r, c - 1));
        
        grid[r][c] = origin; // backtrack
        return maxGold + origin;
    }
}

Runtime: 13 ms, faster than 95.20% of Java online submissions for Path with Maximum Gold.
Memory Usage: 36.5 MB, less than 68.59% of Java online submissions for Path with Maximum Gold.

루션이 ㄹㅇ 제꺼랑 비슷해 보여서 제 스타일대로 좀 바꿔봤는데 이건 되네요..
뭐가 잘못된건지.......^^.......