首页 > 代码库 > leetcode 152. Maximum Product Subarray --------- java
leetcode 152. Maximum Product Subarray --------- java
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
.
找出最大的相乘的数字,很简单,代码还可以优化的地方很多。但是速度还可以。
public class Solution { public int maxProduct(int[] nums) { int len = nums.length; if( nums.length == 1) return nums[0]; int[] result = new int[2]; int target = 0; int left_right = 0,right_left = 0; for( int i = 0 ; i < len ; i ++){ if( nums[i] == 0){ target = Math.max(target,result[0]); result[0] = 0; result[1] = 0; target = 0; }else if( nums[i] > 0 ){ if( result[0] != 0) result[0] *= nums[i]; else result[0] = nums[i]; }else if( nums[i] < 0 ){ if( result[1] == 0 ){ result[1] = nums[i]*(result[0] == 0?1:result[0]); result[0] = 0; } else{ if( result[0] == 0){ result[0] = result[1]*nums[i]; result[1] = 0; }else{ result[0] = result[0]*result[1]*nums[i]; result[1] = 0; } } } left_right = Math.max(Math.max(result[0],target),left_right); } target = 0; result[0] = 0; result[1] = 0; for( int i = len-1;i>=0;i--){ if( nums[i] == 0){ target = Math.max(target,result[0]); result[0] = 0; result[1] = 0; target = 0; }else if( nums[i] > 0 ){ if( result[0] != 0) result[0] *= nums[i]; else result[0] = nums[i]; }else if( nums[i] < 0 ){ if( result[1] == 0 ){ result[1] = nums[i]*(result[0] == 0?1:result[0]); result[0] = 0; } else{ if( result[0] == 0){ result[0] = result[1]*nums[i]; result[1] = 0; }else{ result[0] = result[0]*result[1]*nums[i]; result[1] = 0; } } } right_left = Math.max(Math.max(result[0],target),right_left); } return Math.max(left_right,right_left); } }
leetcode 152. Maximum Product Subarray --------- java
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。