191. Maximum Product Subarray

Leave a comment

August 20, 2016 by oneOokay

Product: 乘法。乘法的特殊性:由于负数的存在很可能最小的一跃而成最大的值,所以要两个array,一个存min,一个存max。

 

public int maxProduct(int[] nums) {
int[] max = new int[nums.length];
int[] min = new int[nums.length];
max[0] = min[0] = nums[0]; //初始化
int result = nums[0]; 
for (int i = 1; i < nums.length; i ++) {
max[i] = min[i] = nums[i]; //先初始化,很可能自身就是最大值

if (nums[i] > 0){
max[i] = Math.max(max[i], max[i – 1] * nums[i]);
min[i] = Math.min(min[i], min[i – 1] * nums[i]);
}else
{
max[i] = Math.max(max[i], min[i – 1] * nums[i]);
min[i] = Math.min(min[i], max[i – 1] * nums[i]);
}
result = Math.max(result, max[i]);
}
return result;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: