By

Contents
  1. 1. 一维数组的最大连续子序列和
  2. 2. 一维数组的最大连续乘积
  3. 3. 二维数组的连续最大子数组和（待更新）

一维数组的最大连续子序列和

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

For example, given the array [−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray [4,−1,2,1] has the largest sum = 6.

思路：假如输入数组为{1,-2,3,10,-4,7,2,-5}，我们尝试从头到尾累加其中的正数，初始化和为0，第一步加上1，此时和为1，第二步加上-2，此时和为-1，第三步加上3，此时我们发现-1+3=2，最大和2反而比3一个单独的整数小，这是因为3加上了一个负数，发现这个规律以后我们就重新作出累加条件：如果当前和为负数，那么就放弃前面的累加和，从数组中的下一个数再开始计数。

1
2
3
4
5
6
7
8
9
10
11
12
//即local[i + 1] = Max(local[i] + A[i], A[i]);
//global[i + 1] = Max(local[i + 1], global[i])
public static int maxSubArray(int[] nums){
    int local = nums[0];
    int global =  nums[0];
    for(int i=1; i<nums.length; i++){
        local = Math.max(local + nums[i], nums[i]);
        global = Math.max(global,local);
    }
    return global;
    
}

一维数组的最大连续乘积

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.

思路：由于同时存在正负数，所以需要存两个值，当前最大和当前最小，当前最小为一个负数时候乘以一个很大的复数可能会变成最大。
因此，当前最大和当前最小会从三种情况中获得：
$$maxPositive[i]= max( max(maxPositive[i-1]a[i],a[i]) , minNegative[i-1]a[i])$$ 内括号是a[i]>0的情况，minp[i-1]a[i] 是a[i]<0的情况
$$minNegative[i] = min(min(maxPositive[i-1]a[i],a[i]),minNegativea[i])$$ 内括号是a[i]<0的情况，minproducta[i] 是a[i]>0的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxProduct(int[] a) {
    int maxproduct = a[0];
    int minproduct = a[0];
    int temp;
    int global=a[0];
    for(int i = 1 ; i < a.length; i++){
        temp = maxproduct;
        maxproduct = Math.max(Math.max(maxproduct*a[i],a[i]),minproduct*a[i]);
        minproduct = Math.min(Math.min(temp*a[i],a[i]),minproduct*a[i]);
        global = Math.max(maxproduct,global);
    }
    return global;
}

二维数组的连续最大子数组和（待更新）

Contents
  1. 1. 一维数组的最大连续子序列和
  2. 2. 一维数组的最大连续乘积
  3. 3. 二维数组的连续最大子数组和（待更新）