23.01.18 Today’s Leetcode

918. Maximum Sum Circular Subarray

Time Limit Exceeded at 94/111 testcases.
DP를 이용해서 풀어보려고 했으나, 1 <= n <= 3*10^4 이라는 contradiction에서 걸려버려서 다른방식으로 풀어야 한다.

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        res = -math.inf
        n = len(nums)
        temp = [[0 for x in range(n)] for y in range(n)]
        for i in range(n):
            temp[i][i] = nums[i]
            for j in range(i, n - 1):
                temp[i][j + 1] = temp[i][j] + nums[j + 1]
            for j in range(i):
                temp[i][j] = temp[i][n - 1] + temp[0][j]
        # print(temp)
        for x in range(n):
            for y in range(n):
                res = max(res, temp[x][y])
        return res

그냥 단순하게 생각해서 적어본 풀이 : Time Limit Exceeded at 96/114 testcases

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        res = -math.inf
        n = len(nums)
        for i in range(n):
            temp = 0
            for j in range(n):
                temp += nums[(i + j) % n]
                res = max(res, temp)
        return res

DP Solution

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        Sum = sum(nums)
        
        # First element is for maximum subarray.
        # Second element is for the minimum subarray.
        dp = [[0,0] for _ in range(len(nums))]

        # Base case for find the maximum subarray.
        dp[0][0] = nums[0]
        res = nums[0]
        for i in range(1,len(nums)):
            dp[i][0] = max(dp[i-1][0]+nums[i], nums[i])
            dp[i][1] = min(dp[i-1][1]+nums[i], nums[i])
            res = max(res, dp[i][0], Sum - dp[i][1])
        return res