[LeetCode] 918. Maximum Sum Circular Subarray

 Problem : https://leetcode.com/problems/maximum-sum-circular-subarray/

In a circular integer, the maximum sum of sub-array can exists in 2 parts:

AAABBBBA'A'A'

It may either exist in the contiguous sub-array [BBBB] or exists in the sub-array [A'A'A'AAA] which combined by the front and rear sub-arrays. 

It is easy to get maximum value of [BBBB].

The maximum value of [A'A'A'AAA] = total value - minimum value of [BBBB]

When the maximum value of [BBBB] <= 0, all numbers in the given array must <= 0.

The the total value == minimum 

The maximum sum of sub-array can only exist in [BBBB].

class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        // maximum value of contiguous sub-array
        var mx = nums[0]
        var mxSoFar = nums[0]
        
        // minimum value of contiguous sub-array
        var mi = nums[0]
        var miSoFar = nums[0]
        
        for (i in 1 until nums.size) {
            mxSoFar = maxOf(mxSoFar + nums[i], nums[i])
            mx = maxOf(mx, mxSoFar)
            
            miSoFar = minOf(miSoFar + nums[i], nums[i])
            mi = minOf(mi, miSoFar)
        }
        
        // if mx > 0 :
        //     the maximum value either exists in one contiguous sub-array
        //     or existis in the combination of the front sub-array 
        //     and rear sub-array (= total - miSoFar)
        // if mx <= 0 :
        //     all numbers in the input array <= 0.
        //     mx is the maximum sum of sub-array 
        return if (mx > 0) maxOf(mx, nums.sum() - mi) else mx 
        
    }
}