[Mock] Google 12

674. Longest Continuous Increasing Subsequence

Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing.

A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].

My Answer 1: Accepted (Runtime: 72 ms - 82.78% / Memory Usage: 15.3 MB - 55.53%)

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        ans = 0
        tmp = 1
        for i in range(1, len(nums)):
            if nums[i-1] >= nums[i]:
                ans = max(ans, tmp)
                tmp = 0
            tmp += 1
            
        ans = max(ans, tmp)
        
        return ans

이전 값과 비교해서 상승세인지 확인

상승세가 꺾이면 ans 에 max 값 update 하고 그 순간부터 길이 다시 계산

Solution 1: Accepted (Runtime: 72 ms - 82.78% / Memory Usage: 15.4 MB - 14.51%)

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        ans = 0
        anchor = 0
        
        for i in range(len(nums)):
            if i and nums[i-1] >= nums[i]:
                anchor = i
            ans = max(ans, i - anchor + 1)
            
        return ans

Sliding Window

i - anchor + 1 로 길이 계산

---

1219. Path with Maximum Gold

In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Return the maximum amount of gold you can collect under the conditions:

• Every time you are located in a cell you will collect all the gold in that cell.
• From your position, you can walk one step to the left, right, up, or down.
• You can't visit the same cell more than once.
• Never visit a cell with 0 gold.
• You can start and stop collecting gold from any position in the grid that has some gold.

My Answer 1: Accepted (Runtime: 1568 ms - 41.95% / Memory Usage: 14.2 MB - 91.21%)

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        def func(i, j, sumGold):
            if i < 0 or i > len(grid)-1 or j < 0 or j > len(grid[0])-1 or grid[i][j] <= 0:
                self.maxGold = max(self.maxGold, sumGold)
                return
            
            tmp = grid[i][j]
            grid[i][j] = -1
            
            if i > 0:
                func(i-1, j, sumGold+tmp)
            if i < len(grid)-1:
                func(i+1, j, sumGold+tmp)
            if j > 0:
                func(i, j-1, sumGold+tmp)
            if j < len(grid[0])-1:
                func(i, j+1, sumGold+tmp)
            
            grid[i][j] = tmp
            
        
        self.maxGold = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] != 0:
                    func(i, j, 0)
        
        return self.maxGold

backtracking 써서
path 끝마다 누적 gold 의 max 값 update

지나간 grid 는 -1 로 값 변경해주고 마지막에 다시 원래 값으로 돌려놓기

My Answer 2: Accepted (Runtime: 1416 ms - 60.98% / Memory Usage: 14.4 MB - 17.92%)

class Solution:
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        def func(i, j):
            if i < 0 or i > len(grid)-1 or j < 0 or j > len(grid[0])-1 or grid[i][j] <= 0:
                return 0
            
            tmp = grid[i][j]
            grid[i][j] = -1
            
            maxGold = 0
            if i > 0:
                maxGold = max(maxGold, func(i-1, j))
            if i < len(grid)-1:
                maxGold = max(maxGold, func(i+1, j))
            if j > 0:
                maxGold = max(maxGold, func(i, j-1))
            if j < len(grid[0])-1:
                maxGold = max(maxGold, func(i, j+1))
            
            grid[i][j] = tmp
            
            return maxGold + tmp
            
        
        ans = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] != 0:
                    ans = max(ans, func(i, j))
        
        return ans

같은 방식인데 재귀함수 밖의 변수에 직접 update 하기보다는
return 값을 줘서 update 하기

---

뭔가 그리디도 생각나서...
다른 방식으로도 풀어보려했는데

1. grid[i][j] 의 사방 중에 max 값을 골라서 재귀 돌리기
   max 값으로 간다고 항상 maximum gold 가 되지 X

2. 가장 긴 path 일 때 self.maxGold update
   path 가 길다고 항상 maximum gold 가 되지 X

그냥 다 봐야하는 듯..
루션이도 DFS backtracking 으로 푼다.