Maximum Product Subarray

FightForProgrammer

于 2014-11-06 13:09:42 发布

阅读量597

点赞数

分类专栏： LeetCode 文章标签： leetcode 动态规划 dp maxProduct

本文链接：https://blog.csdn.net/FightForProgrammer/article/details/40859367

版权

LeetCode 专栏收录该内容

44 篇文章

订阅专栏

LeetCode 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.

题意：求最大连乘积，

解法：DP

//动态规划：最大连续乘积子数组
//思路：1、出现最大连续乘积的可能性有两个：累乘的最大值碰到一个正数；累乘的最小值碰到一个负数
//2、如果累乘得到的最大（最小）值同当前数字相乘之后，没有当前元素大（小），则累乘从当前元素开始
int maxProduct(int A[], int n)
{
	int res = A[0];
	int tmpMax = A[0];
	int tmpMin = A[0];

	for(int i=1; i<n; i++)
	{
		int tMax = tmpMax * A[i];
		int tMin = tmpMin * A[i];

		tmpMax = max(A[i], max(tMax, tMin));
		tmpMin = min(A[i], min(tMax, tMin));

		res = max(tmpMax, res);
	}

	return res;
}