[array] maximum product subarray

✅ Problem

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

 

✅ Approach & Solution

방식)

부분 배열 원소들의 최대 곱 구하기

플로우

• 현재 위치에서의 Max, Min을 구한다.
  • subarray 이어야 하므로 연속된 값이 필요하여 현재 위치에서의 Max, Min을 따로 계산함 
  • 음수 값에 따라 결과가 달라지기 때문에 Min 값도 트래킹해야 함 (이전까지 음수였고 그 다음 값이 음수이면 곱했을 때 양수가 되는 경우)
• for문으로 Max, Min을 업데이트한다.
• Global Max를 구한다. (정답값)

class Solution {
    public int maxProduct(int[] nums) {
        int max = Integer.MIN_VALUE;

        int curMax = 1, curMin = 1;
        for (int n : nums) {
            int temp = curMax * n;
            curMax = Math.max(temp, Math.max(curMin * n, n));
            curMin = Math.min(temp, Math.min(curMin * n, n));

            max = Math.max(max, curMax);
        }

        return max;
    }
}