[Day6] Maximum Product Subarray

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

Maximum Product Subarray - LeetCode

 

<문제 설명>

int형 배열이 있다. 그 배열의 서브배열 중 곱이 가장 큰 서브 배열을 찾자.

 

<풀이 과정>

곱하는 것이기 때문에 양수일 때, 음수일 때를 나누어야 한다.

그리고 전체 합의 시작을 배열의 첫번째로 설정해야한다. 왜냐하면 곱하는 것이기 때문에 0일 경우를 고려해야하기 때문이다. 양수일 경우는 max는 곱한 뒤 현재 전체 곱의 연산을 비교해서 큰 값을 넣어주고 min은 작은 값을 넣어주면 된다. 음수일 경우 max를 곱하면 수가 더 작아지기에 그 값을 min에 넣고 min을 곱한 값을 max에 넣어주면 된다.

 

<풀이 코드>

class Solution {
    public int maxProduct(int[] a) {
        if (a == null || a.length == 0)
            return 0;

        int ans = a[0], min = ans, max = ans;
  
        for (int i = 1; i < a.length; i++) {
            if (a[i] >= 0) {
                max = Math.max(a[i], max * a[i]);
                min = Math.min(a[i], min * a[i]);
            } else {
                int tmp = max;
                max = Math.max(a[i], min * a[i]);
                min = Math.min(a[i], tmp * a[i]);
            }
    
            ans = Math.max(ans, max);
        }
        
        return ans;
    }
}