152 Largest SubArray Product

(Largest SubArray Product: 来code)

Given an unsorted array of doubles, find the subarray that has the greatest product. Return the product.

Examples

• {2.0, -0.1, 4, -2, -1.5}, the largest subarray product is 4(-2)(-1.5) = 12

Analysis

Induction rule:

max[i] = max product of subarray ending at index i = max(max[i-1] * array[i], min[i-1] * array[i], array[i]);

min[i] = min product of subarray ending at index i = min(max[i-1] * array[i], min[i-1] * array[i], array[i]);

Loop through the array, each time remember the max and min value for the previous product, the most important thing is to update the max and min value: we have to compare among max * A[i], min * A[i] as well as A[i], since this is product, a negative * negative could be positive.

Solution

public double largestProduct(double[] array) {
    if (array.length == 0) {
        return 0;
    }
    double max = array[0], min = array[0], result = array[0];
    for (int i = 1; i < array.length; i++) {
        double temp = max;
        max = Math.max(Math.max(max * array[i], min * array[i]), array[i]);
        min = Math.min(Math.min(temp * array[i], min * array[i]), array[i]);
        result = Math.max(max, result);
    }
    return result;
}