918. Maximum Sum Circular Subarray
- Hardness: \(\color{orange}\textsf{Medium}\)
- Ralated Topics:
Array、Divide and Conquer、Dynamic Programming、Queue、Monotonic Queue
一、題目
Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.
A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].
A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.
Example 1:
- Input: nums = [1,-2,3,-2]
- Output: 3
- Explanation: Subarray [3] has maximum sum 3.
Example 2:
- Input: nums = [5,-3,5]
- Output: 10
- Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10.
Example 3:
- Input: nums = [-3,-2,-3]
- Output: -2
- Explanation: Subarray [-2] has maximum sum -2.
Constraints:
n == nums.length1 <= n <= 3 * 10^4-3 * 10^4 <= nums[i] <= 3 * 10^4
二、分析
- 這一題是 [53. MaximumSubArray] 的進階題，如果沒有解題方向的話可以先解看看這題。
- 可以取 circular 代表，可以取頭尾合併，去掉中間的子序列，換個方式思考就是求「總和-最小子序列」。
- 注意子序列至少要有一個元素，故當最小子序列等於總和是，要特別處理
三、解題
1. DP
- Time complexity: \(O(n)\)
- Space complexity: \(O(1)\)
int maxSubarraySumCircular(vector<int>& nums) {
int neg_cur = INT_MAX;
int pos_cur = INT_MIN;
int total = 0;
int neg_max = INT_MAX;
int pos_max = INT_MIN;
for (int i = 0; i < nums.size(); i++) {
neg_cur = neg_cur > 0 ? nums[i] : (neg_cur + nums[i]);
pos_cur = pos_cur < 0 ? nums[i] : (pos_cur + nums[i]);
neg_max = min(neg_cur, neg_max); // 記錄最小子序列
pos_max = max(pos_cur, pos_max); // 記錄最大子序列
total += nums[i]; // 記錄總和
}
if (total == neg_max) return pos_max; // 當總和等於最小子序列時，因為至少需拿一個元素，特例處理
return max(pos_max, total - neg_max); // 解為最大子序列或總和-最小子序列(環狀)
}