competitive-programming2022년 3월 6일1분 분량

[LeetCode] 918. Maximum Sum Circular Subarray 풀이

수정일: 2022년 3월 6일

Dynamic programming

지원 언어:enko

#Problem

918. Maximum Sum Circular Subarray

#Approach

이 문제는 ** $LeetCode$ 53. Maximum Subarray**의 심화 버전입니다.
유일한 차이점은 주어진 nums 배열이 순환하는지 여부입니다.

대상 부분 배열은 두 가지 형태가 될 수 있습니다.

감싸는(wrapped around) 부분 배열

이 경우, 가운데에 있는 나머지 부분 배열의 합은 항상 최소가 됩니다.

그 외

따라서 최대 합은 max(maxSubarraySum, totalSum-minSubarraySum)으로 계산할 수 있습니다.
왼쪽에서 오른쪽으로, maxSubarraySum과 minSubarraySum을 각각 계산하고, 최종 정답을 계산합니다.

Note
다음 코너 케이스를 생각해 봅시다: nums 배열의 모든 원소가 음의 정수인 경우.

#Code

typedef vector<int> vi;

class Solution {
private:
    const int NEG_INF= -1e5;
    const int POS_INF= 1e5;

public:
    int maxSubarraySumCircular(vi &nums) {
        int n= nums.size(), totalSum= 0, maxSum= NEG_INF, minSum= POS_INF;
        int curMax= NEG_INF, curMin= POS_INF;
        for (int i=0; i < n; ++i) {
            curMax= max(nums[i], curMax+nums[i]);
            maxSum= max(maxSum, curMax);
            curMin= min(nums[i], curMin+nums[i]);
            minSum= min(minSum, curMin);
            totalSum += nums[i];
        }
        if (maxSum < 0) return maxSum;
        return max(maxSum, totalSum-minSum);
    }
};

#Complexity

Time: $O(N)$
Space: $O(1)$