22.12.14 Today’s Leetcode

198. House Robber (Medium)

Dynamic Programming 과 DFS를 이용한 풀이

int dfs(int* nums, int* dp, int start, int len) {
    if (start >= len)
        return 0;
    if (dp[start] != -1)
        return dp[start];
    int i;
    int res = 0;
    for(i = start; i < len; i++) {
        int temp = nums[i] + dfs(nums, dp, i + 2, len);;
        if (temp > res)
            res = temp;
    }
    dp[start] = res;
    return res;
}

int rob(int* nums, int len){
    int dp[len + 10];
    for (int i = 0; i < len; i++)
        dp[i] = -1;
    return dfs(nums, dp, 0, len);
}

152. Maximum Product Subarray

Subarray와 관련된 문제가 많이 나오는데, 어제 풀었던 XOR 문제처럼 production은 inversion이 production이므로 arrayy를 만들어서 구현하면 될거라고 생각했다. 하지만 element가 0 인경우 와 여러 문제점이 발생해서 조금 어려움이 있었다. zero_index 를 이용해서 0이 발견되었을때 array 를 두 개로 쪼개서 생각했고 1, -1이 반복되어서 같은 값이 나오는 경우를 고려하여 mul.append(temp)에서 mul에 같은 값이 있는지 확인하는 조건을 넣었다.

class Solution:

    def maxProduct(self, nums: List[int]) -> int:
        mul = [] # mul[i] : product i to n
        temp, before = 1, -10**9
        zero_break = -1
        for i, num in enumerate(nums):
            if num == 0:
                zero_break = i
                break
            temp *= num
            if temp not in mul:
                before = temp
                mul.append(temp)

        print(mul)

        n = len(mul)
        res = -10**9
        for i in range(len(nums)):
            res = max(res, nums[i])

        for i in range(n):
            res = max(res, mul[i])

        for i in range(n - 1):
            for j in range(i + 1, n):
                cur = mul[j] // mul[i]
                res = max(res, cur)

        if zero_break != -1:
            res = max(res, 0)
            res = max(res, self.maxProduct(nums[zero_break + 1:]))
        return res