Maximum Product Subarray

DP문제를 계속 풀다보면은 솔직히 헷갈리는 부분들이 더 많고 가끔은 이게 왜 DP지? 하는 류의 문제도 있다. 가끔은 2중 룹으로 DP를 다뤄야할 때도 있고 가끔은 한번의 룹으로 모든걸 기록할 수도 있다. 이번 분제 같은 경우는 한번의 룹으로 모든걸 해결할 수도 있지만 아무 생각 없이 하다가는 답을 틀린다. 일단 이 문제는 Negative 숫자가 포함된 인풋을 준다. 이 말은, 바로 전에 최고 숫자만 기록하다가는 마이너스와 마이너스를 곱해야 하는 문제에서 최고값을 기록 못한다는 뜻이다.

즉, 이 문제의 핵심은 바로 전에 최고 값만 구하는게 아니고 최저 값도 함께 구해서 과연 현재의 값에서 최고 값을 곱했을때, 혹은 최저값을 곱했을때의 값을 비교하고 가장 큰 기록을 남기는게 핵심인것이다. 문제를 풀면서도 하나의 DP테이블로는 부족하다고 생각했는데 역시 MIN 값을 저장할 수 있는 MIN_DP가 필요했고 로직을 잘 설계할 필요가 있었다.

class Solution {
    public int maxProduct(int[] nums) {
        int[] dp = new int[nums.length]; 
        int[] min_dp = new int[nums.length]; 
        dp[0] = nums[0]; 
        min_dp[0] = nums[0]; 
        
        for(int i = 1; i < nums.length; i++){
            int tmp = dp[i-1]; 
            dp[i] = Math.max(nums[i],Math.max(dp[i-1] * nums[i],min_dp[i-1] * nums[i])); 
            min_dp[i] = Math.min(Math.min(tmp * nums[i], min_dp[i-1] * nums[i]), nums[i]);
        }

        return Collections.max(Arrays.stream(dp).boxed().toList());
    }
}