152. Maximum Product Subarray - Medium

前往題目

想法

• 毫無想法，每次看到這種subarray都覺得是不是backtracking🤣

思路

這題的解法也很妙

1. 使用min和max紀錄每個點的當前最小值和最大值，紀錄最小值的原因是有可能遇到負數，但如果再遇到一個就會變成正數，所以也要考慮進去
2. 疊代nums，每個迴圈都判斷是否有更小和更大的值

這題蠻不像DP，但他的確是DP🥺

Code

class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length == 1) return nums[0];

        int res = -11;
        int currMin = 1, currMax = 1;

        for (int num : nums) {
            int tempMin = currMin * num;
            currMin = Math.min(Math.min(tempMin, currMax * num), num);
            currMax = Math.max(Math.max(tempMin, currMax * num), num);
            res = Math.max(res, currMax);
        }

        return res;
    }
}

2024/04/21

• 本來想說要用prefix和suffix
• 但只要紀錄最小值與最大值就行

class Solution {
    public int maxProduct(int[] nums) {
        // Base case
        if (nums.length == 1) return nums[0];

        int res = -11;
        int curMin = 1, curMax = 1;

        for (int num : nums) {
            // Probably negative or positive
            int tempMin = curMin * num;
            // Probably min gets smaller or larger if it becomes positive
            curMin = Math.min(Math.min(tempMin, curMax * num), num);
            curMax = Math.max(Math.max(tempMin, curMax * num), num);
            res = Math.max(res, curMax);
        }

        return res;
    }
}