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.length
  • 1 <= 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);                       // 解為最大子序列或總和-最小子序列(環狀)
}

回目錄 Catalog