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=0，解决方法有两种：
1.根据0的分布把数组分为几部分，每部分都不含0，分别求最大值，最后选最大的（若数组有0，且各部分比较结果是负数时，结果要取0）
2.每乘一个数都要保存最大值，当遇到0时，记录当前状态的变量置0
由于1需要存储0的位置，给程序带来额外开销，所以2较好
2.负数的存在会导致较小（大）的局部解后边可能会成为较大（小）的解，解决方法有两种（由于遇上0的问题已经解决，所以这里的算法都是在没有0的情况下）：
1.配合1.1使用，统计负数个数，双数时直接把这部分全部相乘，单数时取【最后一个负数前所有值相乘结果】
和【第一个负数之后所有值相乘结果】这两个值的较大者
2.*动态规划的方法：设置最终解变量res和局部解变量max和min，局部变量设置两个的原因是负数的存在，动态方程：
当前值是正数时，max（i） = max（max（i-1）* nums(i),nums(i)）,min(i) = min(min（i-1）* nums(i),nums(i))
当前值是负数时，max(i) = max（min（i-1）* nums(i),nums(i)） ,min(i) = min(max（i-1）* nums(i),nums(i))
比较之后可以发现，只要当遇上负数时，将max和min两个变量交换，则状态方程可以统一*/
动态规划：

public int maxProduct1(int[] nums) {
if (nums == null || nums.length == 0) return 0;
//全局解
int res = nums[0];
for (int i = 1, max = res, min = res; i < nums.length; i++) {
if (nums[i] < 0) {
int temp = max;
max = min;
min = temp;
}
//状态方程
max = Math.max(max * nums[i], nums[i]);
min = Math.min(min * nums[i], nums[i]);

        if (max > res) res = max;  
    }

    return res;  
}

操作数组方法：

public int maxProduct2(int[] nums) {
if (nums.length == 1)
return nums[0];
int res = 0;
//数组记录0的位置
List l = new ArrayList<>();
for (int i = 0;i < nums.length;i++)
{
if (nums[i] == 0)
l.add(i);
}
//没有0的情况
if (l.size() == 0)
return product(0,nums.length,nums);
//有0的情况
else
{
//分为几部分求解
res = Math.max(res,product(0,l.get(0),nums));
for (int i = 1; i < l.size(); i++) {
res = Math.max(res,product(l.get(i-1)+1,l.get(i),nums));
}
res = Math.max(res,product(l.get(l.size()-1)+1,nums.length,nums));
return Math.max(res,0);
}

}  
public int product(int sta,int end,int\[\] nums)  
{  
    if (sta > nums.length-1)  
        return 0;  
    if (end - sta <= 1)  
        return nums\[sta\];  
    int loc = 1;  
    int num = 0;  
    int index = 0;  
    //数组记录第一个负数和最后一个负数的位置  
    List<Integer> l = new ArrayList<>();  
    for (int i = sta;i < end;i++)  
    {  
        if (nums\[i\] < 0)  
        {  
            num++;  
            l.add(i);  
        }

    }  
    //双数情况  
    if (num%2 == 0)  
    {  
        for (int i = sta;i < end;i++) {  
            loc \*= nums\[i\];  
        }  
        return loc;  
    }  
    //单数情况  
    else  
    {  
        int loc1 = 1;  
        int loc2 = 1;  
        for (int i = sta;i < l.get(l.size()-1);i++ )  
        {  
            loc1 \*= nums\[i\];  
        }  
        for (int i = l.get(0)+1;i < end;i++)  
        {  
            loc2 \*= nums\[i\];  
        }  
        return Math.max(loc1,loc2);  
    }  
}