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.
【题目分析】
给定一个整数数组，找出数组中的一个子序列，使得序列中所有元素的乘积最大。
【思路】
观察发现数组中的元素可以分为三类：正数，负数和零。我们找到如下几种情况：
情况1：数组中没有0元素，而且数组中负数的个数为偶数。
解决方法：直接返回数组中各个元素的乘积；
情况2：数组中没有0元素，而且数组中负数的个数为奇数。
解决方法：计算第一个负数数之后所有元素的乘积pro1和最后一个负数之前的所有元素乘积pro2，返回较大值。
情况3：数组中含有0元素。
解决方法：用0元素把数组分为若干段，对每一段使用情况1和情况2中的方法进行处理。
【java代码】
public class Solution {
public int maxProduct(int[] nums) {
if(nums.length == 0) return 0;
int prezero = -1, curzero = -1;
int maxpro = Integer.MIN_VALUE;
for(int i = 0; i < nums.length; i++){ //找到数组中的0元素，把数组分为不包含0的若干段进行处理
if(nums[i] == 0){
prezero = curzero;
curzero = i;
maxpro = Math.max(product(nums, prezero+1, curzero-1), maxpro);
}
}
if(curzero < nums.length - 1) maxpro = Math.max(product(nums, curzero+1, nums.length-1),maxpro);
if(maxpro > 0 || curzero == -1) return maxpro; //如果最大值大于零或者数组中没有0，直接返回找到的最大值
else return 0; //否则返回0，此时maxpro<=0 && curzero != 0
}
public int product(int[] num, int start, int end){
if(start > end || start < 0 || end < 0) return Integer.MIN_VALUE;
int firstneg = -1, lastneg = -1, pro = 1; //firstneg表示第一个负数的下标，lastneg表示最后一个负数的下标
for(int i = start; i <= end; i++){
pro *= num[i];
if(num[i] < 0){
if(firstneg == -1) firstneg = i;
lastneg = i;
}
}
if(pro > 0 || start == end) return pro; //如果找到的值大于零或者数组中只有一个元素则直接返回结果
int pro1 = pro, pro2 = pro; //否则计算第一个负数数之后所有元素的乘积pro1和最后一个负数之前的所有元素乘积pro2
for(int i = start; i <= firstneg; i++){
pro1 /= num[i];
}
for(int i = lastneg; i <= end; i++){
pro2 /= num[i];
}
return pro1 > pro2 ? pro1 : pro2; //返回较大值
}
}
效果：
