算法學習-資料結構-2.4.3最大子序列的和問題

問題描述：求一串數列中，子序列最大和；相對應的是最小子序列和問題，類似

算法一：暴力求解，時間複雜度O(N^3)，不推薦

算法二：采用“分治”政策，複雜度O(NlogN)，體會思想。最大子序列和可能出現在左、中、右。

#include <iostream>
#include <vector>
using namespace std;
int subSeqMax(const int arr[], int n);
int subProMax(const int arr[], int startIndex, int endIndex);
template<typename T>
int length(T& arr)
{
	return sizeof(arr) / sizeof(arr[0]);
}

int main()
{
	int arr[8] = { -2, 6, -1, 5 ,4 ,-7, 2 ,3 };//答案為14
	int n = length(arr);
	int subMax = subSeqMax(arr, length(arr));
	cout << "最大和：" << subMax << endl;
	system("pause");
	return 0;
}

int subSeqMax(const int arr[], int n)
{
	int startIndex = 0;
	int endIndex = n - 1;
	int max = subProMax(arr, startIndex, endIndex);
	return max;
}

int subProMax(const int arr[], int startIndex, int endIndex)
{
	int pivot = (startIndex + endIndex) / 2;

	if (startIndex == endIndex)//退出遞歸的基準條件
	{
		return arr[startIndex];
	}
	int leftMax = 0, rightMax = 0;
	leftMax = subProMax(arr, startIndex, pivot);
	rightMax = subProMax(arr, pivot + 1, endIndex);
	//處理最大和在中間的情況
	int leftBorderMax = 0, rightBorderMax = 0;
	int leftBorderSum = 0, rightBorderSum = 0;
	int leftBorderIndex, rightBordIndex;
	//從基準開始，求左邊最大和和右邊最大和
	for (int i = pivot; i >= startIndex; i--)
	{
		leftBorderSum += arr[i];
		if (leftBorderMax < leftBorderSum)
			leftBorderMax = leftBorderSum;
	}
	for (int i = pivot + 1; i <= endIndex; i++)
	{
		rightBorderSum += arr[i];
		if (rightBorderSum > rightBorderMax)
			rightBorderMax = rightBorderSum;
	}
	//求最大的一個作為結果
	int middleMax = leftBorderMax + rightBorderMax;
	int max = 0;
	if (middleMax > leftMax)
		max = middleMax;
	else max = leftMax;

	if (max < rightMax)
		max = rightMax;
	return max;
}
           

算法三：比較巧妙，一個優點是隻對資料進行一次掃描

int maxSubSeqSum(const int arr[], int n)
{
	int maxSum, thisSum;
	maxSum = thisSum = 0;
	for (int i = 0; i < n; i++)
	{
		thisSum += arr[i];
		if (maxSum < thisSum)
			maxSum = thisSum;
		else if (thisSum < 0)
			thisSum = 0;
	}
	return maxSum;
}
           

算法四：采用動态規劃，複雜度O(N)

很多動态規劃算法非常像數學中的遞推。我們如果能找到一個合适的遞推公式，就能很容易的解決問題。

我們用dp[n]表示以第n個數結尾的最大連續子序列的和，于是存在以下遞推公式：

dp[n] = max(0, dp[n-1]) + num[n]

仔細思考後不難發現這個遞推公式是正确的，則整個問題的答案是

max(dp[m]) | m∈[1, N]

。C語言代碼如下：

note：存放dp[n]的數組和num[]共用一個，節省了空間，但破壞了輸入數組！

//動态規劃
#include <stdio.h>
//N是數組長度，num是待計算的數組，放在全局區是因為可以開很大的數組
int N, num[134217728];
int main()
{
	//輸入資料
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> num[i];	
	int ans = 0;
	for (int i = 0; i < N; i++)
	{
		if (num[i] > 0) 
			num[i + 1] += num[i];
		if (num[i + 1] > ans) 
			ans = num[i + 1];
	}
	cout << ans << endl;
	system("pause");
	return 0;
}
           

這裡我們沒有建立dp數組，根據遞歸公式的依賴關系，單獨一個num數組就足以解決問題，建立一個一億長度的數組要占用幾百MB的記憶體！這個算法的時間複雜度是O(N)的，是以它計算一億長度的序列也不在話下！不過你如果真的用一個這麼大規模的資料來測試這個程式會很慢，因為大量的時間都耗費在程式讀取資料上了！