數對之差最大

問題：給定數組 a0,a1,a2...an ，求前一個元素減掉後一個元素的差組成的集合的最大值。

這個問題不是最大值最小值問題，因為不能确定最大值是不是在最小值前面。

設最終所求結果為 F。

1.先給出一種較易想到的方法。用動态規劃方法。

設所求為 F ，現在假設與 ai 相關聯的 F 是 Fi，能不能求出 Fi+1 呢？倘若可以有這樣一個式子，便可在依次求 F 的過程中，儲存最大的 F ，即是所求。深入思考，如果用 Fi 關聯被減數（即 u - v 算式中的 u），那麼，由于無法确定被減數是否已經被周遊過了（即，是否包含在 0 ~ i 個元素中），這不利于動态規劃算式的展開。

動态規劃實施過程中，應該讓後一個待求量包含前面已求量的所有資訊。

是以可以用 Fi 關聯減數，這樣可以保證被減數被周遊過，如此建構的動态規劃狀态轉移方程有足夠的資訊。如圖 1 給出一個狀态轉移圖。

圖1 由 i 到 (i + 1)狀态轉移

由上圖知，Fi 轉移到 Fi+1 ，設 u 是 0 ~ i - 1中的最大元素的下标，有兩種可能，第一種是 Fi+1 = u 元素減去 i + 1 元素。第二種是一種特殊情況，i 元素比 u 元素大，Fi+1 = i 元素減去 i+1 元素。

這便是狀态轉移方程。如此，問題可解。

2.再給出分冶的解法。

如果現在給定了兩個數組 A , B，為了求這兩個數組拼接後的數組的 F，必須要知道哪些條件？顯然，需要：

1).A 的 F 和 B 的 F，

2).A 中的最大值，B 中的最小值

實際上，1) 中的條件說明最終給出最大之差的兩個元素都在 A 中，或者 B 中，通過對比 AF , BF 的大小确定哪一個是最終結果。而 2) 中的條件說明最終給出最大之差的兩個元素，較大元素 max 在 A 中，較小元素 min 在 B 中，此時，max 必然是 A 中的最大值，min 必然是 B 中的最小值。

是以形成如下解法：

采用分冶的解法，将數組劃分為左右兩個數組，分别求出其 max，min ，F ，将這些值合并到合并數組的對應的值，則問題可解。

3.最後給出一種技巧性的解法。問題是求左邊元素減右邊元素的最大值，即求 ：a0 - a1 ， a1 - a2 ，a2 - a3，......這些值組成的集合 S 中，連續元素相加之和最大值。先證明這兩個問題是等價的。

證明：如果 ai - aj 在考慮的範圍内，由于 ai - aj  = (ai - ai+1) + (ai+1 - ai+2) + ... + (aj-1 - aj)，是以 ai - aj 可以被轉換為求 S 中連續的從 i 到 j-1 元素的和。

由于每一個差都能轉換為 S 集合的多個連續的元素的和，是以，考慮原數組差集合中的最大值，等價于 S 集合中多個連續元素的和的最大值。

證畢！

之前有一篇文章就是描述的這個問題：http://blog.csdn.net/lizhihaoweiwei/article/details/37739421

至此，問題得到解決。

最後給出這三種方法的解法的原代碼。

//動态規劃解法
int solutionDP(int *data,int nLength)
{
	if(1 == nLength)
	{
		return *(data);
	}
	int max = *(data);
	int curDiff = *(data) - *(data + 1);
	int maxDiff = curDiff;
	for (int i = 2;i < nLength;++ i)
	{
		if(max < *(data + i - 1))
		{
			max = *(data + i - 1);
		}

		curDiff = max - *(data + i);

		if(maxDiff < curDiff)
		{
			maxDiff = curDiff;
		}
	}
	return maxDiff;
}

//分冶解法
#define INFINITESIMAL -999999999;
int solutionDiv(int *data,const int startPos,const int endPos,int *max,int *min)
{
	if(startPos == endPos)
	{
		*min = *max = *(data + startPos);
		return INFINITESIMAL;
	}
	int mid = (startPos + endPos) / 2;
	int leftMax,leftMin;
	int leftMaxDiff = solutionDiv(data,startPos,mid,&leftMax,&leftMin);
	int rightMax,rightMin;
	int rightMaxDiff = solutionDiv(data,mid + 1,endPos,&rightMax,&rightMin);

	*max = leftMax > rightMax ? leftMax : rightMax;
	*min = rightMin < leftMin ? rightMin : leftMin;
	int maxDiff = leftMaxDiff > rightMaxDiff ? leftMaxDiff : rightMaxDiff;
	if(leftMax - rightMin > maxDiff)
	{
		maxDiff = leftMax - rightMin;
	}
	return maxDiff;	
}

//轉換為數組最大連續元素和解法
int solutionMaxSum(int *data,int nLength)
{
	if(1 == nLength)
	{
		return *(data);
	}
	if(2 == nLength)
	{
		return *(data) - *(data + 1);
	}
	int *subs = new int[nLength - 1];
	for (int i = 1;i < nLength;++ i)
	{
		*(subs + i - 1) = *(data + i - 1) - *(data + i);
	}

	int curDiff = 0,maxDiff = *(subs);
	
	for (int i = 0;i < nLength - 1;++ i)
	{
		maxDiff = curDiff > maxDiff ? curDiff : maxDiff;
		curDiff += *(subs + i);
		if(0 > curDiff)
		{
			curDiff = 0;
		}
		
	}
	return maxDiff;
}