Daily LeetCode Challenge - 918. Maximum Sum Circular Subarray

Problem From.

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

오늘 문제는 앞과 뒤가 이어져있는 circular interger array 에서 subarray 를 구했을때, 그 subarray 의 합이 가장 큰 경우를 구하는 문제였다.

가장 큰 subarray 를 구하는 문제는 Kadane's algorithm 을 통해서 구할 수 있는데 DP 의 한 종류였다.
(Kadane's algorithm - https://medium.com/@rsinghal757/kadanes-algorithm-dynamic-programming-how-and-why-does-it-work-3fd8849ed73d)

이 문제에서는 circular interger array 라는 부분이 다른 점이었는데 두 가지 경우로 나뉘게 된다.

1. 기존의 이어지지 않은 부분인 array 에서 최대값이 구해지는 경우
   이 경우에는 kadane's algorithm 을 통해 구해진 최대값을 반환하면 된다.
2. 이어진 array 즉 기존 array 의 끝부분과 첫 부분이 이어진 부분이 포함되어 최대값이 구해지는 경우
   이 경우에는 한가지 다른 개념을 적용해야 하는데, 이 경우에 구해지는 최대값을 구하고 나면, 중간에 남아있는 부분은 min subarray 즉 그 합이 최소가 되는 subarray 가 만들어진다는 점이었다.
   결국 어레이의 모든 값의 합에서 min subarray 를 빼면 max subarray 가 만들어지는 구조였다.

따라서 이 문제를 풀기 위해서는 max subarray 와 min subarray 를 모두 구한 다음,
local min 을 구했을 때가 array 의 합과 같으면 max subarray 를 반환하고
아니라면 기존 array 의 합에서 min subarray 를 뺀 값과 max subarray 를 비교하여 더 큰 값을 반환하면 되는 문제였다.

class Solution {
    fun maxSubarraySumCircular(nums: IntArray): Int {
        
        var localMax = 0
        var globalMax = nums[0]
        var localMin = 0
        var globalMin = nums[0]
        
        for(i in 0 until nums.size) {
            
            localMax = Math.max(nums[i], localMax + nums[i])
            if(localMax > globalMax) {
                globalMax = localMax
            }
            localMin = Math.min(nums[i], localMin + nums[i])
            if(localMin < globalMin) {
                globalMin = localMin
            }
            
        }
        
        return if(localMin == nums.sum()) globalMax else Math.max(globalMax, nums.sum() - globalMin)
        
    }
}

위 풀이의 시간 복잡도는 O(N) 이 된다.