[leetCode] 152. Maximum Product Subarray 카단 알고리즘의 변형

저번 leetCode에서 풀었던 Maximum Subarray와 비슷한 문제이다. 때문에 기존에 익혔던 카단 알고리즘을 사용하면 되지만 변수가 존재한다. Product는 곱으로서 음수와 음수의 곱은 양수가 되고 양수에 음수를 곱하게 되면 음수가 되기 때문에 이 경우의 수를 대비하여 최대 값을 구해 주어야 한다. 

 

카단 알고리즘은 쉽게 말하면 현재 값으로만 이루어진 어레이와 이전 어레이+현재값으로 이루어진 서브 어레이의 비교라고 할 수 있다. 

class Solution {
    func maxProduct(_ nums: [Int]) -> Int {
        
        var num = nums
        
        var maxP = num[0]
        var minP = num[0]
        var answer = num[0]
        
        for i in 1..<num.count {
            
            let tmpMax = maxP
            
            maxP = max(num[i], maxP * num[i], minP * num[i])
            minP = min(num[i], tmpMax * num[i], minP * num[i])
            
            answer = max(maxP, answer)
        }
        
        return answer
    }
}

처음에 maxP 바뀌는 걸 생각 못해서 조금 헷갈렸는데 tmpMax로 받아서 사용했다. 그리고 num[0]으로 배열 첫 자리의 값을 가지고 왔는데 num.first가 훨씬 코드 보기 편한거 같다.