[LeetCode] 152. Maximum Product Subarray

 

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

Maximum Product Subarray - LeetCode

 

 

아래 코드는 브루트포스로 스스로 해결하였고, 아래 주석 코드는 투 포인터를 활용한 다른 사람 코드이다. 사실 시간이 그렇게 차이가 나지 않기 때문에 어떤 방법을 사용해도 무관하다는 생각이 들지만 다른 방식으로 접근해보는 것도 좋은 공부법이라고 생각한다. 

 

class Solution {
    public int maxProduct(int[] nums) {
        // 2ms : bruteforce
        int mx = nums[0], mn = nums[0], ans = nums[0];

        for(int i=1; i<nums.length; i++) {
            int tmp = mx;

            mx = Math.max(Math.max(mx * nums[i], mn * nums[i]), nums[i]);
            mn = Math.min(Math.min(tmp * nums[i], mn * nums[i]), nums[i]);
            
            if(mx > ans) ans = mx;
        }

        return ans;


        // 1ms : two pointer
        // int n = nums.length;
        // int l = 1, r = 1;
        // int ans = nums[0];

        // for(int i=0; i<n; i++) {
        //     l = l==0 ? 1 : l;
        //     r = r==0 ? 1 : r;

        //     l *= nums[i]; // prefix
        //     r *= nums[n-1-i]; // suffix

        //     ans = Math.max(ans, Math.max(l, r));
        // }
        // return ans;
    }
}