【LeetCode刷题Java版】Maximum Product Subarray

时间:2014-10-24 13:01:03   收藏:0   阅读:314

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.


package com.liuhao.acm.leetcode;

/**
 * @author liuhao 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.
 * 
 */
public class MaximumProductSubarray {

	public static int maxProduct(int[] A) {
		int len = A.length;

		if (len <= 0) {
			return 0;
		}

		if (len == 1) {
			return A[0];
		}

		int max = A[0];
		int min = A[0];
		int result = A[0];

		for (int i = 1; i < len; i++) {
			int max_temp = max * A[i];
			int min_temp = min * A[i];
			max = Math.max(A[i], Math.max(max_temp, min_temp));
			min = Math.min(A[i], Math.min(max_temp, min_temp));
			result = Math.max(result, max);
		}

		return result;
	}

	public static void main(String[] args) {
		int[] a = new int[] { -4,-3 };
		System.out.println(maxProduct(a));
	}

}


原文:http://blog.csdn.net/bruce_6/article/details/40425509

评论(0
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!