Description

Find the contiguous subarray within an array (containing at least one number) which has the largest product.Have you met this question in a real interview?

Example

For example, given the array[2,3,-2,4], the contiguous subarray[2,3]has the largest product =6

Solution

public class Solution {
    /*
     * @param nums: a list of integers
     * @return: A integer indicate the sum of minimum subarray
     */
    public int minSubArray(List<Integer> nums) {
        // write your code here
        if (nums == null || nums.size() == 0) {
            return 0;
        }

        int[] sum  = new int[nums.size() + 1];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.size(); i++) {
            sum[i + 1] = Math.min(nums.get(i), sum[i] + nums.get(i));
            min = Math.min(min, sum[i + 1]);
        }

        return min;
    }
}