918. Maximum Sum Circular Subarray
Đề Bài
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 * 104-3 * 104 <= nums[i] <= 3 * 104
Lời Giải
C++
0918-maximum-sum-circular-subarray.cpp
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
const int oo = 1e5;
int minSub = oo;
int ansMin = oo;
int maxSub = -oo;
int ansMax = -oo;
int s = 0;
for (int num : nums) {
minSub = min(num, minSub + num);
ansMin = min(ansMin, minSub);
maxSub = max(num, maxSub + num);
ansMax = max(ansMax, maxSub);
s += num;
}
if (ansMax < 0) {
return ansMax;
}
return max(s - ansMin, ansMax);
}
};
Python
0918-maximum-sum-circular-subarray.py
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
maxSub = -10**5
maxSum = -10**5
minSub = 10**5
minSum = 10**5
total = 0
for num in nums:
maxSum = max(num, maxSum + num)
maxSub = max(maxSub, maxSum)
minSum = min(num, minSum + num)
minSub = min(minSub, minSum)
total += num
return max(maxSub, total - minSub) if maxSub > 0 else maxSub