Question
from lintcode
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example
For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.
Idea
We all know that a max/min value can be retrieved by a loop.
You need to keep track of three things:
- global max: the final answer
- contiguous max: the max product adjacent to the current value in the loop
- contiguous min: the min product adjacent to the current value in the loop, you want to keep this because it might become next contiguous maximum (sign production rule: - * - = +)
public class Solution {
/**
* @param nums: an array of integers
* @return: an integer
*/
public int maxProduct(int[] nums) {
// edge case
if (nums.length == 0) {
return 0;
}
// previous
int prevContiguousMax = nums[0], prevContiguousMin = nums[0];
int contiguousMax, contiguousMin;
int globalMax = nums[0];
// for each number
for (int i = 1; i < nums.length; i ++) {
contiguousMax =
Math.max(nums[i], Math.max(prevContiguousMin * nums[i], prevContiguousMax * nums[i]));
contiguousMin =
Math.min(nums[i], Math.min(prevContiguousMin * nums[i], prevContiguousMax * nums[i]));
globalMax = Math.max(globalMax, contiguousMax);
prevContiguousMin = contiguousMax;
prevContiguousMax = contiguousMin;
}
return globalMax;
}
}
