題目： LeetCode - 918. Maximum Sum Circular Subarray

題目說明

給一個陣列，求此陣列的最大子陣列和。( 可以循環 )

解題思路

  • 想法： 最大子陣列和可能會有兩種情況，一種是沒有跨過頭尾，就是單純的最大子陣列和。另一種是有跨過頭尾，這時的和就是 陣列和 - 最小子陣列和。

  • 作法： 使用一個迴圈得到最大子陣列和及最小子陣列和，最後比對 sum - mn 及 max 何者較大即可。需要注意的是，若是最小值 mn 和 sum 相等，代表整個陣列都是負的，這時需要直接回傳 max。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// fast IO
static auto __ = []()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int mx = INT_MIN, mn = INT_MAX, currMax = 0, currMin = 0, sum = 0;
        for(auto i : A)
        {
            currMax = max(currMax + i, i);
            currMin = min(currMin + i, i);
            mx = max(currMax, mx);
            mn = min(currMin, mn);
            sum += i;
        }
        return sum == mn ? mx : max(sum - mn, mx);
    }
};