5.30号刷题

发表于 | 分类于 | 0 comments

第一题 152. Maximum Product Subarray

算法

O(n)的复杂度，从后往前遍历整个数组，然后记录下当前的最大值和最小值

maxnow = Math.max(Math.max(maxpre * nums[i], minpre * nums[i]),nums[i]);
minow = Math.min(Math.min(minpre * nums[i], maxpre * nums[i]), nums[i]);

这一步可以更新当前最大最小值，如果为0的话，max和min都可以清除为0，非常关键的一步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int maxProduct(int[] nums) {
        if (nums.length < 1) return 0; 
        int maxpre = nums[0], minpre = nums[0], maxsofar = nums[0], maxnow, minow;
        
        for (int i = 1; i < nums.length; i++) {
            maxnow = Math.max(Math.max(maxpre * nums[i], minpre * nums[i]),nums[i]);
            minow = Math.min(Math.min(minpre * nums[i], maxpre * nums[i]), nums[i]);
            maxsofar = Math.max(maxnow, maxsofar);
            maxpre = maxnow;
            minpre = minow;
        }
        
        return maxsofar;        
    }
}