[파이썬 PYTHON · 자바 JAVA] LeetCode【Maximum Product Subarray】

Maximum Product Subarray - LeetCode

---

자바 코드

class Solution {
    public int maxProduct(int[] nums) {
        int [] dp = new int[nums.length];
        int [] maxValue = new int[nums.length];
        int [] minValue = new int[nums.length];

        dp[0] = nums[0];
        maxValue[0] = nums[0];
        minValue[0] = nums[0];
        int ans = nums[0];
        for(int i=1;i<nums.length;i++){
            maxValue[i]=Math.max(Math.max(nums[i],maxValue[i-1]*nums[i]),minValue[i-1]*nums[i]);
            minValue[i]=Math.min(Math.min(nums[i],maxValue[i-1]*nums[i]),minValue[i-1]*nums[i]);

            dp[i] = maxValue[i];
            ans = Math.max(ans,dp[i]);
        }


        return ans;
    }
}

파이썬 코드

class Solution(object):
    def maxProduct(self, nums):
        
        _max = nums[0]
        _min = nums[0]
        ans = nums[0]

        for i in range(1,len(nums)):
            maxResult = max(max(nums[i],_max*nums[i]),_min*nums[i])
            minResult = min(min(nums[i],_max*nums[i]),_min*nums[i])
            
            _max = maxResult
            _min = minResult

            ans = max(ans,maxResult)

        return ans

 

곱셈의 경우 덧셈과 비슷하지만, 음수인 최솟값에 음수가 곱해지면 양수가 되는 상황까지 고려해야한다.

 

따라서 _max 값은 nums[i] 와  _max*nums[i] 와 _min*nums[i] 값 중 가장 큰 값을 기록해야한다.

 

_min값 역시, nums[i] 와 _max*nums[i] 와 _min*nums[i] 값 중 가장 작은 값을 기록해야한다.

 

연산이 끝난 뒤, ans를 최댓값으로 계속 갱신하면 된다.