[Algorithm] LeetCode - Maximum Product Subarray

📠 문제

• Maximum Product Subarray
• 난이도 Medium
• 부분배열중 가장 곱이 높은 배열을 찾는 문제

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

💡 풀이

이 문제의 고민은 만약에 부분합이라면 투포인터를 사용할 수 있지만 부분 곱셈에서는 조금 까다로운 문제가 있었다.

1. 배열의 요소 중 하나라도 0이 나왔을 땐 무조건 곱이 0이 되므로 포인터를 움직이며 비교할 수 없다는 것.
2. 음수는 같은 음수를 만나면 오히려 더 높은 숫자가 나올 수 있다는 것.

결국 아래와 같이 maxBuffer, minBuffer를 두어 해결하고자 했다. 또한 0일 경우를 고려해서 아무것도 곱하지 않은 num부터도 가능하게 했다. 이렇게 푸니 O(n)의 시간복잡도로 풀 수 있었다.

func maxProduct(_ nums: [Int]) -> Int {
    var result = nums[0]
    var maxBuffer = 1
    var minBuffer = 1

    for num in nums {
        let candidates = [num, maxBuffer * num, minBuffer * num]
        maxBuffer = candidates.max() ?? 1
        minBuffer = candidates.min() ?? 1
        result = max(result, maxBuffer)
    }

    return result
}

참고로 메모리부분은 이렇게 간단한 문제는 아래와 같이 똑같은 코드를 돌려도 그때그때 격차가 큰 것 같다.