918. Maximum Sum Circular Subarray

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int maxSubarraySumCircular(vector<int>& nums) {
        
        //  5   -3  5   
        //  5   -3  2   
        // 尋找最大非循環子陣列 與 最大循環子陣列  = total sum - 最小和的子陣列
        
        int global_mx = INT_MIN, local = 0;
        local = 0;
        for(int n:nums){
            local = max(n, local+n);
            global_mx =  max(global_mx, local);
        }
        int global_mn = INT_MAX;
        local = 0;
        
        int total = 0;
        for(int n:nums){
            total+=n;
            local = min(n+local, n);
            global_mn = min(local, global_mn);
            
        }
        if( total == global_mn) return global_mx;
        return max(global_mx, total - global_mn);
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)