Maximum Product Subarray

문제

https://leetcode.com/problems/maximum-product-subarray/description/

입력

1 <= nums.length <= 2 * 10^4
-10 <= nums[i] <= 10

결과

ans: Int = 곱 부분 배열의 최댓값

해석

이전 maxSubarray는 단순 합이라, 흐름이 하나였지만

곱은 말 그대로 음수와 양수에 따른 흐름이 2개이므로 변수가 하나 더 필요했다.

그래서 음수를 고려한 최대 음수 변수와, 최대 양수 변수를 계속 가져가며 반복마다 갱신한다.

코드

class Solution {
    func maxProduct(_ nums: [Int]) -> Int {
        let n = nums.count

        if n == 1 {
            return nums[0]
        }

        var minProduct = nums[0] // 음수 최댓값
        var maxProduct = nums[0] // 양수 최댓값
        var ans = nums[0]

        for i in 1..<n {
            let now = nums[i]
            let candidate = [now, minProduct * now, maxProduct * now]
            minProduct = candidate.min()!
            maxProduct = candidate.max()!
            ans = max(ans, maxProduct)
        }
    
        return ans
    }
}