O(n)解法以及细节问题152. Maximum Product Subarray

为什么要初始化int max = 1; int min = 1;不是0或者Integer.MAX_VALUE Integer.MIN_VALUE。 这个方法max和min到底是怎么样在更新的,细节分析

为什么要初始化为1, 这个跟product except self那道题很像,只需要想到i = 0的时候,我们更新max和min时要如何更新呢,比如max = Math.max(nums[i], Math.max(max*nums[i], min*nums[i]));那我们这里很明显地知道要选最大的话,max,min都要初始化为1才合理。因为nums[i]前面没有数,又要得到一个有效的可选数,是乘积的话肯定选1,和的话就选零。很intuitive。

然后注意到我们这个max, min的意思是
max: ending at index i, the maximum subarray product
min: ending at index i, the minimun subarray product
也就是说,我们遍历完整个数组,以每一个数组元素结尾的subarray乘积都算过一次了,更新出来的res就是要求的解。

class Solution {
    public int maxProduct(int[] nums) {
        int max = 1;
        int min = 1;
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++){
            int temp = max;
            max = Math.max(nums[i], Math.max(max*nums[i], min*nums[i]));
            min = Math.min(nums[i], Math.min(temp*nums[i], min*nums[i]));
            if (max > res){
                res = max;
            }
        }
        return res;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容