[leetCode] 53. Maximum Subarray with Swift 카단 알고리즘으로 쉽게 구하기

leetCode 53은 모든 원소의 값의 합이 최대값을 가지는 서브 어레이를 구하는 것이 목표입니다. 이때 서브 어레이는 연속성을 가져야 하는데, 이 뜻은 중간 인덱스를 뛰어 넘지 않고 인덱스 순서대로 되어 있는 어레이입니다. 그렇기 때문에 배열에서 최대값들의 조합만을 찾아 구하는 것이 아니며 어떤 서브 어레이가 가장 최고의 값을 가지고 있는지 구하는 것이 이 문제에 포인트 입니다. 

 

서브 어레이의 최대값을 구하는 문제에서 많이 언급되는 알고리즘은 Kadane 알고리즘입니다. 

reference Youtube video here 👇

우선 문제에서 주어진 [-2, 1, -3, 4, -1, 2, 1, -5, 4]를 봅시다. 여기서 첫번째 4를 중점으로 보겠습니다. 현재 인덱스는 3이고 그 인덱스의 값은 4입니다. 이때 올 수 있는 서브 어레이의 조합을 봅니다. [-2, 1, -3] 을 K라 하고 [1, -3]을 M이라 하겠습니다. 각각 서브 어레이의 합은 -4 그리고 -2입니다. 즉 어떤 배열의 전체 원소의 합이 더 큰가 하면 K < M 인 것입니다. 이제 현재 원소를 각 서브 어레이에 더해 준다고 합시다.

 

그렇다면 K+[4], M+[4 ]가 되고 이는 K < M이기 때문에 당연히 K+[4] < M+[4]가 됩니다. 이제 아무런 값도 없는 empty array인 []를 생각해 봅시다. 배열은 E라고 합니다. 위의 개념과 같이 생각하면 K + [4](현재 인덱스 값] < E + [4](현재 인덱스 값) 이라 한다면 E+[4] 서브 배열이 K+[4] 서브 배열 보다 큰 것이 됩니다(이때 크다는 것은 배열의 각 원소들의 합을 말합니다). E는 빈 배열이므로 [4]가 서브 배열 중 큰 배열이 되는 것이죠. 

 

현재 인덱스 시점에서 이전 서브 어레이들과 현재 인덱스 합으로 구해진 값보다 현재 인덱스의 값(현재 인덱스의 값으로만 이루어진 서브 배열)이 더 크다면 현재 인덱스의 값 부터 시작하는 서브 어레이가 큰 것이 됩니다. 반대의 상황이라면 그 반대로 이전 서브 어레이 + 현재 어레이가 전체 어레이 중 가장 큰 값을 가지는 서브 어레이가 되는 것입니다. 

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var num = nums
        var answer: Int = num[0]
        
        for i in 1..<num.count {
            num[i] = max(num[i], num[i]+num[i-1])
            answer = max(answer, num[i])
        }
        
        return answer
    }
}