2023.01.18 Today's Challenge

https://leetcode.com/problems/maximum-sum-circular-subarray/

Maximum Sum Circular Subarray - LeetCode

일단 아이디어는 다음과 같다.
1. index 1부터 n-1까지 진행하면서 누적합을 구해 놓는다. 그러면서 max 값도 같이 저장해놓음.
2. 누적합 리스트를 다시 index 1부터 n-1까지 진행하면서 index 의 값을 빼면서 현재 max랑 비교해서 업데이트 한다.

틀렸다. 한 30분 트러블 슈팅 했는데 안되서 그냥 솔루션 보고 품.

결론은 DP로 푸는거였음 =_=

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        s = sum(nums)
        dp = [[0,0] for _ in range(len(nums))]
        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], s - dp[i][1])
        return res