LeetCode.152 Maximum Product Subarray

LeetCode.152 Maximum Product Subarray。

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array[2,3,-2,4],

the contiguous subarray[2,3]has the largest product =6.

分析：

class Solution {
    public int maxProduct(int[] nums) {
        //查找字串中最大子序列(该序列的乘起来最大)
        //这个算法是许多聪明的算法
        //该算法的优点是，它只对数据进行一次扫描，一旦nums[i]被读入并被处理
        //它就不再需要记忆。
        //乘法需要考虑负负得正
        int max = nums[0], min=nums[0];
        int thisSum=nums[0];
		for (int j = 1; j < nums.length; j++) {
            
            //乘以一个负数 max和min交换
            if(nums[j]<0){
                int temp=max;
                max=min;
                min=temp;
            }
            
            //求最大值和最小值
            max=Math.max(nums[j],max*nums[j]);
            min=Math.min(nums[j],min*nums[j]);
            
            
            if(max>thisSum){
                thisSum=max;
            }
            
		}
		return thisSum;
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        //求子序列中乘积最大的值（子序列为连续）
        int max = nums[0];
        int prod = 1;
        //正序扫一遍
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == 0) {
                //若乘数为0，表示之前全部归0，被乘数置为1，下同理
                prod = 1;
                max = Math.max(max, 0);
            }
            else {
                prod *= nums[i];
                max = Math.max(max, prod);
            }
        }
        prod = 1;
        //倒序扫一遍
        for (int i = nums.length - 1; i >= 0; --i) {
            if (nums[i] == 0) prod = 1;
            else {
                prod *= nums[i];
                max = Math.max(max, prod);
            }
        }
        //得出正序和倒序的最大值 即为结果
        return max;
        
    }
}