hanyeah

动态规划——最大连续子段和

动态规划题目（三）——最大连续乘积子串

最大连续字段和

问题描述： 给定一个数组，记录一串数字，可正可负，现要求出其中最大的连续子段和。 

用数组A[N]记录所要求的数组，用数组B[N]来记录连续子段和的状态 

通过分析，可以知道： 

当B[K]>0时，无论B[K]为何值，B[K]=B[K-1]+A[K] 

当B[K]<0时，也就是B[K]记录到一个A[J]是负的，可以把B[K]变成负的，那么B[J]记录的这一段应该截掉，应为无论后面的A[K]多大，加上个负数总不可能是最大的子段和，因此将B[K]=A[K]，重新开始记录。 

 故动态转移方程便可得出 

 B[K] = MAX(B[K-1]+A[K] , A[K]) 

 看个实例

k      1     2       3        4
a[k]  3     -4       2        10
b[k]  3     -1       2        12

必须记住B[K]是状态量，要获得最大连续子段和，只需在数组B中扫描一遍得到最大的数即可。

注：

时间复杂度O(n)，空间复杂度O(n)。

代码：

var a = [3, -4, 2, 10];
console.log(findMaxProduct(a));
/**
 * 求最大子串和。
 */
function findMaxProduct(a){
	var b = [];
	var max = a[0];
	var len = a.length;
	b[0] = a[0];
	for(var k = 1; k < len; k++){
		b[k] = Math.max(b[k-1] + a[k], a[k]);
		max = Math.max(b[k], max);
	}
	return max;
}

很容易看出来，其实数组b不是必须的，空间复杂度O(1)。

改进之后：

var a = [3, -4, 2, 10];
console.log(findMaxProduct(a));
/**
 * 求最大子串和。
 */
function findMaxProduct(a){
	var max = a[0];
	var b = a[0];
	var len = a.length;
	for(var k = 1; k < len; k++){
	    b = Math.max(b + a[k], a[k]);
		max = Math.max(b, max);
	}
	return max;
}

最大连续字段积

题目描述    

给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。也就是说，上述数组中，3 0.5 8这3个数的乘积30.58=12是最大的，而且是连续的。

动态规划求解题目的时候最重要的是要找到状态转移方程！

针对这道题目，我们使用两个变量记录当前最大值maxEnd, 和当前最小值minEnd。为什么记录当前最小值呢？因为数组中会出现负数，乘以一个负数的话，当前最小值是会逆袭的！！

然后就是状态转移方程中对这两个变量的更新：

maxEnd=max(max(maxEnd*a[i], minEnd*a[i]), a[i]); //更新当前最大值 

minEnd=min(min(maxEnd*a[i], minEnd*a[i]), a[i]); //更新当前最小值

注：

时间复杂度O(n)，空间复杂度O(1)。

代码如下：

var a = [-2.5, 4, 0, 3, 0.5, 8, -1];
console.log(findMaxProduct(a));
/**
 * 求最大子串。
 */
function findMaxProduct(a){
	var max = a[0];
	var min = a[0];
	var maxProduct = a[0];
	var len = a.length;
	for(var k = 1; k < len; k++){
		var a0 = Math.max(max*a[k], min*a[k], a[k]);
		var b0 = Math.min(max*a[k], min*a[k], a[k]);
		max = a0;min = b0;
		maxProduct = Math.max(max, maxProduct);
	}
	return maxProduct;
}