매일 LeetCode 풀기 | Maximum Product Subarray

 

Given an integer array nums, find a 
subarray
 
that has the largest product, and return
 
the product
.

The test cases are generated so that the answer will fit in a 32-bit integer.
 
Example 1:
Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
 
Constraints:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

 

저번에 푼 부분배열이랑 같은 원리라서, 유레카 하고 풀었는데.. 음수의 경우를 고려하지 않아서 틀렸던 문제. 음수까지 고려할려니 조금 어렵게 느껴지기도 했다. 

 

기존 코드 

class Solution {
    func maxProduct(_ nums: [Int]) -> Int {
        var current = nums[0]
        var maxTotal = nums[0]

        for i in 1..<nums.count {
            current = max(nums[i], current * nums[i])
            maxTotal = max(maxTotal, current)
        }

        return maxTotal
    }
}

 

배운 코드 

class Solution {
    func maxProduct(_ nums: [Int]) -> Int {
        var maxProduct = nums[0]
        var minProduct = nums[0]
        var maxTotal = nums[0] 

        for i in 1..<nums.count {
            let temp = maxProduct

            maxProduct = max(nums[i], max(maxProduct * nums[i], minProduct * nums[i]))
            minProduct = min(nums[i], min(temp * nums[i], minProduct * nums[i]))
            
            maxTotal = max(maxTotal, maxProduct)
        }

        return maxTotal
    }
}

 

접근 방식 
1. 지금까지 계산의 가장 큰 값을 담는 maxProduct, 지금까지 계산의 가장 작은 값을 담는 minProduct, 최종 최대 값을 구하는 maxTotal 변수를 선언한다. 
2. 반복문을 돈다. 
2-1. maxProduct : (지금까지 계산의 최대값 * 현재 원소) & (지금까지 계산의 최소값 * 현재 원소) 중 최대값을 현재 원소와 비교해 더 큰 값을 저장한다. 
2-2. minProduct: (지금까지 계산의 최대값 * 현재 원소) & (지금까지 계산의 최소값 * 현재 원소) 중 최소값을 현재원소와 비교해 더 작은 값을 저장한다. 
2-3. maxProduct 와 minProduct 중 최대 값을 최종 maxTotal 에 저장한다.