LeetCode 解題紀錄 918. Maximum Sum Circular Subarray

Maximum Sum Circular Subarray - LeetCode

題目

給定一個長度為 n 的整數陣列 nums，要求返回環狀子陣列中可形成的的最大總和

條件

• 1 ≤ n ≤ 3*10⁴
• -3*10⁴ ≤ nums[i] ≤ 3*10⁴

觀察

• Kadane’s Algorithm可以找出子陣列裡的最大和，可以解決沒有跨越邊界的 case
• 而有跨越邊界的情況時，代表開頭與結尾的部份元素可以組成最大值，而剩餘中間的部份必然是最小值
• 使用 Kadane's Algorithm 但相反的條件就可以試著找出最小的子陣列，再以總和減去，就可以得到跨越邊界的最大值
• 返回兩者中最大的

解法(Kadane's Algorithm)

• 第一個迴圈計算正常情況下的最大子陣列和，並計算總和
• 第二個迴全計算反向的 Kadane's algorithm
• 比較較大值，要注意 edge case 是整個陣列都是負值時，這時不存在跨越邊界的子陣列，但程式會計算出 0的子陣列和，反而會出錯

class Solution {
    public int maxSubarraySumCircular(int[] nums) {
        int n = nums.length, max = nums[0];
        int total = 0;
        int sum = 0;     
        // Kadane's algorithm        
        for(int i=0;i<n;i++) {            
            sum += nums[i];
            max = Math.max(max, sum);
            if(sum < 0)
                sum = 0;            
            // 統計總和
            total += nums[i];
        }
        int min = nums[0];
        sum = 0;
        // inverse Kadane's algorithm
        for(int i=0;i<n;i++) {            
            sum += nums[i];
            min = Math.min(min, sum);
            if(sum > 0)
                sum = 0;            
        }
        // 當總和等於最小子陣列時，返回最大值
        return total == min?max:Math.max(max, total-min);
    }
}

結果

TC：O(n)

SC：O(1)