|
最大子序列和問題
問題描述：
輸入一組整數(shù)，求出這組數(shù)字子序列和中最大值。也就是只要求出最大子序列的和，不必求出最大的那個序列。例如：
序列：-2 11 -4 13 -5 -2，則最大子序列和為20。
序列：-6 2 4 -7 5 3 2 -1 6 -9 10 -2，則最大子序列和為16。
算法一：
//窮舉法，復(fù)雜度O(n^3)
long maxSubSum1(const vector<int>& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
for (int j = i; j < a.size(); j++)
{
long thisSum = 0;
for (int k = i; k <= j; k++)
{
thisSum += a[k];
}
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
這是一個O(N^3) 的算法，算法本身很容易理解，而且很直觀的感覺做了很多無用操作。例如：i = 0, j = 3時，會計算a[0] + a[1] +…+ a[3]；而當(dāng)i = 0, j = 4時候又會計算a[0] + a[1] +…a[4]。
算法二：
通過撤出一個for循環(huán)來避免三次時間。
//也是窮舉法，不過減去了上面的一些不必要操作O(n^2)
long maxSubSum2(const vector<int>& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
long thisSum = 0;
for (int j = i; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
這是一個非常直觀的窮舉法（比上面的分析還有簡單些），而且沒有多余重復(fù)的操作，復(fù)雜度為O(N^2) 。其中，thisSum表示a[i] + a[i+1] + … + a[j-1]。
算法三：
對這個問題，有一個相對復(fù)雜的O(NlogN)的解法，就是使用遞歸。如果要是求出序列的位置的話，這將是最好的算法了（因為我們后面還會有個O(N)的算法，但是不能求出最大子序列的位置）。該方法我們采用“分治策略”（divide-and-conquer）。
在我們例子中，最大子序列可能在三個地方出現(xiàn)，或者在左半部，或者在右半部，或者跨越輸入數(shù)據(jù)的中部而占據(jù)左右兩部分。前兩種情況遞歸求解，第三種情況的最大和可以通過求出前半部分最大和（包含前半部分最后一個元素）以及后半部分最大和（包含后半部分的第一個元素）相加而得到。
//遞歸法，復(fù)雜度是O(nlogn)
long maxSumRec(const vector<int>& a, int left, int right)
{
if (left == right)
{
if (a[left] > 0)
return a[left];
else
return 0;
}
int center = (left + right) / 2;
long maxLeftSum = maxSumRec(a, left, center);
long maxRightSum = maxSumRec(a, center+1, right);
//求出以左邊對后一個數(shù)字結(jié)尾的序列最大值
long maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; i--)
{
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
//求出以右邊對后一個數(shù)字結(jié)尾的序列最大值
long maxRightBorderSum = 0, rightBorderSum = 0;
for (int j = center+1; j <= right; j++)
{
rightBorderSum += a[j];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum);
}
long maxSubSum3(const vector<int>& a)
{
return maxSumRec(a, 0, a.size()-1);
}
另外max3(long,long,long)表示求三個long中的最大值：
//求出三個long中的最大值
long max3(long a, long b, long c)
{
if (a < b)
{
a = b;
}
if (a > c)
return a;
else
return c;
}
對這個算法進行分析：
T(1) = 1
T(N) = 2T(N/2) + O(N)
最后得出算法的復(fù)雜度為：O(NlogN) 。
下面介紹一個線性的算法，這個算法是許多聰明算法的典型：運行時間是明顯的，但是正確性則很不明顯（不容易理解）。
//線性的算法O(N)
long maxSubSum4(const vector<int>& a)
{
long maxSum = 0, thisSum = 0;
for (int j = 0; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
return maxSum;
}
很容易理解時間界O(N) 是正確的，但是要是弄明白為什么正確就比較費力了。其實這個是算法二的一個改進。分析的時候也是i代表當(dāng)前序列的起點，j代表當(dāng)前序列的終點。如果我們不需要知道最佳子序列的位置，那么i就可以優(yōu)化掉。
重點的一個思想是：如果a[i]是負(fù)數(shù)那么它不可能代表最有序列的起點，因為任何包含a[i]的作為起點的子序列都可以通過用a[i+1]作為起點來改進。類似的有，任何的負(fù)的子序列不可能是最優(yōu)子序列的前綴。例如說，循環(huán)中我們檢測到從a[i]到a[j]的子序列是負(fù)數(shù)，那么我們就可以推進i。關(guān)鍵的結(jié)論是我們不僅可以把i推進到i+1，而且我們實際可以把它一直推進到j+1。
舉例來說，令p是i+1到j之間的任何一個下標(biāo)，由于前面假設(shè)了a[i]+…+a[j]是負(fù)數(shù)，則開始于下標(biāo)p的任意子序列都不會大于在下標(biāo)i并且包含從a[i]到a[p-1]的子序列對應(yīng)的子序列（j是使得從下標(biāo)i開始成為負(fù)數(shù)的第一個下標(biāo)）。因此，把i推進到j+1是安全的，不會錯過最優(yōu)解。注意的是：雖然，如果有以a[j]結(jié)尾的某序列和是負(fù)數(shù)就表明了這個序列中的任何一個數(shù)不可能是與a[j]后面的數(shù)形成的最大子序列的開頭，但是并不表明a[j]前面的某個序列就不是最大序列，也就是說不能確定最大子序列在a[j]前還是a[j]后，即最大子序列位置不能求出。但是能確保maxSum的值是當(dāng)前最大的子序列和。這個算法還有一個有點就是，它只對數(shù)據(jù)進行一次掃描，一旦a[j]被讀入處理就不需要再記憶。它是一個聯(lián)機算法。
聯(lián)機算法：在任意時刻算法都能夠?qū)λ炎x入的數(shù)據(jù)給出當(dāng)前數(shù)據(jù)的解。
常量空間線性時間的聯(lián)機算法幾乎是完美的算法。
程序測試：
先通過文件讀寫函數(shù)產(chǎn)生一組隨機數(shù)并且讀入到一個vector<int>中：
//COUNT和MAX_NUM分別表示隨機數(shù)個數(shù)和最大值
const long COUNT = 1000;
const int MAX_NUM = 200;
//讀文件
bool readFile(vector<int>& input, string fileName)
{
ifstream infile(fileName.c_str());
if (!infile)
return false;
int s;
while(infile>>s)
{
input.push_back(s);
}
return true;
}
//寫大量隨機測試數(shù)據(jù)
bool writeTestData(string fileName)
{
ofstream outfile(fileName.c_str());
if (!outfile)
return false;
srand((unsigned)time(NULL));
for (int i = 0; i < COUNT; i++)
{
if (rand() % 2 == 0)
outfile << rand() % MAX_NUM << '\n';
else
outfile << ~(rand() % MAX_NUM) << '\n';
}
return true;
}
測試可得：
當(dāng)COUNT = 1000的時候maxSubSum1()要等10s，后三個很快。
當(dāng)COUNT = 10000的時候maxSubSum2()要等8s，后兩個很快。
當(dāng)COUNT = 1000000的時候maxSubSum3()要等10s，maxSubSum4()要等4s。
其實當(dāng)COUNT = 1000000這個時候但是作文件讀寫就要很耗時了，光是in.txt就達(dá)到了4.7MB了。
而COUNT = 10000000的時候光是文件讀寫就要半分鐘，in.txt達(dá)到了47.2MB，這時候再做maxSubSum3()和maxSubSum4()的比較，maxSubSum4()需要56s，而maxSubSum3()這時候需要85s（包括了讀文件的時間）?？梢姅?shù)據(jù)量比較大的情況下O(NlogN)的遞歸算法也是可行的，并不比O(N)低很多。尤其在要求出最大子序列位置的情況下，分治遞歸算法體現(xiàn)了強大的威力。
程序源碼：
#include <iostream>
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
//COUNT和MAX_NUM分別表示隨機數(shù)個數(shù)和最大值
const long COUNT = 10000;
const int MAX_NUM = 200;
//讀文件
bool readFile(vector<int>& input, string fileName)
{
ifstream infile(fileName.c_str());
if (!infile)
return false;
int s;
while(infile>>s)
{
input.push_back(s);
}
return true;
}
//寫大量隨機測試數(shù)據(jù)
bool writeTestData(string fileName)
{
ofstream outfile(fileName.c_str());
if (!outfile)
return false;
srand((unsigned)time(NULL));
for (int i = 0; i < COUNT; i++)
{
if (rand() % 2 == 0)
outfile << rand() % MAX_NUM << '\n';
else
outfile << ~(rand() % MAX_NUM) << '\n';
}
return true;
}
//窮舉法
long maxSubSum1(const vector<int>& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
for (int j = i; j < a.size(); j++)
{
long thisSum = 0;
for (int k = i; k <= j; k++)
{
thisSum += a[k];
}
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
//也是窮舉法，不過減去了上面的一些不必要操作O(n^2)
long maxSubSum2(const vector<int>& a)
{
long maxSum = 0;
for (int i = 0; i < a.size(); i++)
{
long thisSum = 0;
for (int j = i; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
}
}
return maxSum;
}
//遞歸法，復(fù)雜度是O(nlogn)
long max3(long a, long b, long c)
{
if (a < b)
{
a = b;
}
if (a > c)
return a;
else
return c;
}
long maxSumRec(const vector<int>& a, int left, int right)
{
if (left == right)
{
if (a[left] > 0)
return a[left];
else
return 0;
}
int center = (left + right) / 2;
long maxLeftSum = maxSumRec(a, left, center);
long maxRightSum = maxSumRec(a, center+1, right);
//求出以左邊對后一個數(shù)字結(jié)尾的序列最大值
long maxLeftBorderSum = 0, leftBorderSum = 0;
for (int i = center; i >= left; i--)
{
leftBorderSum += a[i];
if (leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
//求出以右邊對后一個數(shù)字結(jié)尾的序列最大值
long maxRightBorderSum = 0, rightBorderSum = 0;
for (int j = center+1; j <= right; j++)
{
rightBorderSum += a[j];
if (rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum);
}
long maxSubSum3(const vector<int>& a)
{
return maxSumRec(a, 0, a.size()-1);
}
//線性的算法O(N)
long maxSubSum4(const vector<int>& a)
{
long maxSum = 0, thisSum = 0;
for (int j = 0; j < a.size(); j++)
{
thisSum += a[j];
if (thisSum > maxSum)
maxSum = thisSum;
else if (thisSum < 0)
thisSum = 0;
}
return maxSum;
}
int main ()
{
vector<int> input;
/**
if (!writeTestData("in.txt"))
{
cout << "寫文件錯誤" << endl;
}
*/
if (readFile(input, "in.txt"))
{
//cout << maxSubSum1(input) << endl;
//cout << maxSubSum2(input) << endl;
cout << maxSubSum3(input) << endl;
cout << maxSubSum4(input) << endl;
}
return 0;
}
|
