[Kotlin] 릿코드 152 Maximum Product Subarray

📘 문제

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

💡 풀이

처음엔 투포인터, 분할 정복 기법으로 풀려고 했지만, 안 풀려서 다른 접근 방식으로 시도했다.

우선, 문제에서 신경써야 할 부분들을 정리했다.
연속된 배열의 최대 곱을 구하는 것이기 때문에 0과 음수를 생각했다.
0이 나오면 홀수 개의 음수만 있지 않은 이상 답이 될 수 없기에,
0이 나오면 비교 연산하는 변수를 초기화 시키고 다시 최대값 비교를 시켰다.

또 생각할 것은 tmp 변수를 갱신하며 answer 최대값 비교할 것인데,
tmp 변수를 갱신할 때는 순차적으로 갱신한다는 점이다.
그래서 왼쪽부터 시작, 오른쪽 부터 시작 이렇게 두 가지 경우를 따져봐야한다.
{2, -5, -2, -4, 3} 이 배열을 왼쪽부터 곱하면서 최대값 갱신해보고 오른쪽부터 곱하면서 갱신해보면 감이 올 것이다.

💻 코드

import kotlin.math.max

private fun main() {
    println(maxProduct(intArrayOf(-2, 3, -4))) //24
    println(maxProduct(intArrayOf(2, -5, -2, -4, 3))) //24
}

private fun maxProduct(nums: IntArray): Int {

    var answer = Int.MIN_VALUE
    var tmp = 1
    var containZero = false

    for (i in 0 until nums.size) {
        val num = nums[i]
        if (num == 0) {
            containZero = true
            tmp = 1
            continue
        }
        tmp *= num
        answer = max(answer, tmp)
    }
    tmp = 1
    for (i in nums.lastIndex downTo 0){
        val num = nums[i]
        if (num == 0) {
            containZero = true
            tmp = 1
            continue
        }
        tmp *= num
        answer = max(answer, tmp)
    }

    // 0을 기준으로 초기화하므로 {0,-1,0} 같은 경우 예외처리
    if (containZero && answer < 0) return 0
    return answer
}

결과