Maximum Subarray, Maximum Product Subarray

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.

O(n) Solution

• It’s called the Kadane’s Algorithm…

public int maxSubArray(int[] A) {
    int max_so_far = A[0];
    int max_ending_here = A[0];
    for (int i=1;i<A.length;i++){
        max_ending_here+=A[i];
        max_ending_here = Math.max(max_ending_here, A[i]);
        max_so_far = Math.max(max_ending_here, max_so_far);
    }
    return max_so_far;
}

Divide and Conquer Solution O(nlogn)

• more subtle does not mean cleaner…
• divide the given array in two halves and return the maximum of following three
• Maximum subarray sum in left half

• Maximum subarray sum in right half
• Maximum subarray sum such that the subarray crosses the midpoint

public int maxSubArray(int[] A) {
         int l=0, r=A.length-1;
         return rec(A, l, r);
    }
    
    private int rec(int[] A, int l, int r){
        if(l==r) return A[l];
        int m= (l+r)/2; 
        return Math.max(Math.max(rec(A,l,m),rec(A,m+1,r)),cross(A,m,l,r));
    }
    
    private int cross(int[] A, int m, int l, int r){
        int suml=A[m];
        int maxvaluel=A[m];
        for (int i=m-1;i>=l;i--){
            suml+=A[i];
            if(suml>maxvaluel){
                maxvaluel=suml;
            }
        }
        int sumr=A[m];
        int maxvaluer=A[m];
        for (int i=m+1;i<=r;i++){
            sumr+=A[i];
            if(sumr>maxvaluer){
                maxvaluer=sumr;
            }            
        }
        return maxvaluel+maxvaluer-A[m];
    }

---

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.

Near Brute force

• If we store result from i to j in t[i][j], the runtime is O(n^2)

public int maxProduct(int[] A){
	int maxvalue=0;
	for(int i=0;i<A.length;i++){
		for(int j=i;j<A.length;j++){
			int tmp=1;
			for(int k=i;k<=j;k++){
			tmp*=A[k];
					}
			if(tmp>maxvalue){
				maxvalue=tmp;
			}
		}
	}
	return maxvalue;
}

DP? Solution

• There are only two cases when we get a larger result
• mininum(negative) value multiply cur value(which happens to be negative)
• maximum value multiply cur value
• Be careful with the special case when multiplying both would decrease the result, then change start point to self

public int maxProduct(int[] A){
	int maxvalue=A[0];
	int minval=A[0], maxval=A[0];
	for(int i=1;i<A.length;i++){
	    int a=A[i] * minval;
	    int b=A[i] * maxval;
	    maxval=Math.max(Math.max(a,b),A[i]);
	    minval=Math.min(Math.min(a,b),A[i]);
	    maxvalue=Math.max(maxvalue,maxval);
	}
	return maxvalue;
}