最大子序列和问题【转】

发现这个文章写的很好,所以转载了,文章来源:http://www.cnblogs.com/CCBB/archive/2009/04/25/1443455.html

问题描述:

输入一组整数,求出这组数字子序列和中最大值。也就是只要求出最大子序列的和,不必求出最大的那个序列。例如:

序列:-2 11 -4 13 -5 -2,则最大子序列和为20。

序列:-6 2 4 -7 5 3 2 -1 6 -9 10 -2,则最大子序列和为16。

算法一:

 1 //穷举法,复杂度O(n^3) 
 2 long maxSubSum1(const vector<int>& a) 
 3 { 
 4        long maxSum = 0; 
 5        for (int i = 0; i < a.size(); i++) 
 6        { 
 7               for (int j = i; j < a.size(); j++) 
 8               { 
 9                      long thisSum = 0; 
10  
11                      for (int k = i; k <= j; k++) 
12                      { 
13                             thisSum += a[k]; 
14                      } 
15                      if (thisSum > maxSum) 
16                             maxSum = thisSum; 
17               } 
18        } 
19        return maxSum; 
20 } 

这是一个O(N^3) 的算法,算法本身很容易理解,而且很直观的感觉做了很多无用操作。例如:i = 0, j = 3时,会计算a[0] + a[1] +…+ a[3];而当i = 0, j = 4时候又会计算a[0] + a[1] +…a[4]。

算法二:

 1 通过撤出一个for循环来避免三次时间。
 2 
 3 //也是穷举法,不过减去了上面的一些不必要操作O(n^2) 
 4 long maxSubSum2(const vector<int>& a) 
 5 { 
 6        long maxSum = 0; 
 7        for (int i = 0; i < a.size(); i++) 
 8        { 
 9               long thisSum = 0; 
10               for (int j = i; j < a.size(); j++) 
11               { 
12                      thisSum += a[j]; 
13                      if (thisSum > maxSum) 
14                             maxSum = thisSum; 
15               } 
16        } 
17        return maxSum; 
18 }

这是一个非常直观的穷举法(比上面的分析还有简单些),而且没有多余重复的操作,复杂度为O(N^2) 。其中,thisSum表示a[i] + a[i+1] + … + a[j-1]。

算法三:

  对这个问题,有一个相对复杂的O(NlogN)的解法,就是使用递归。如果要是求出序列的位置的话,这将是最好的算法了(因为我们后面还会有个O(N)的算法,但是不能求出最大子序列的位置)。该方法我们采用“分治策略”(divide-and-conquer)。

在我们例子中,最大子序列可能在三个地方出现,或者在左半部,或者在右半部,或者跨越输入数据的中部而占据左右两部分。前两种情况递归求解,第三种情况的最大和可以通过求出前半部分最大和(包含前半部分最后一个元素)以及后半部分最大和(包含后半部分的第一个元素)相加而得到。

 1 //递归法,复杂度是O(nlogn) 
 2 long maxSumRec(const vector<int>& a, int left, int right) 
 3 { 
 4        if (left == right) 
 5        { 
 6               if (a[left] > 0) 
 7                      return a[left]; 
 8               else 
 9                      return 0; 
10        } 
11        int center = (left + right) / 2; 
12        long maxLeftSum = maxSumRec(a, left, center); 
13        long maxRightSum = maxSumRec(a, center+1, right); 
14  
15        //求出以左边对后一个数字结尾的序列最大值 
16        long maxLeftBorderSum = 0, leftBorderSum = 0; 
17        for (int i = center; i >= left; i--) 
18        { 
19               leftBorderSum += a[i]; 
20               if (leftBorderSum > maxLeftBorderSum) 
21                      maxLeftBorderSum = leftBorderSum; 
22        } 
23  
24        //求出以右边对后一个数字结尾的序列最大值 
25        long maxRightBorderSum = 0, rightBorderSum = 0; 
26        for (int j = center+1; j <= right; j++) 
27        { 
28               rightBorderSum += a[j]; 
29               if (rightBorderSum > maxRightBorderSum) 
30                      maxRightBorderSum = rightBorderSum; 
31        } 
32  
33        return max3(maxLeftSum, maxRightSum,  
34               maxLeftBorderSum + maxRightBorderSum); 
35 } 
36  
37 long maxSubSum3(const vector<int>& a) 
38 { 
39        return maxSumRec(a, 0, a.size()-1); 
40 }
41 另外max3(long,long,long)表示求三个long中的最大值:
42 
43 //求出三个long中的最大值 
44 long max3(long a, long b, long c) 
45 { 
46        if (a < b) 
47        { 
48               a = b; 
49        } 
50        if (a > c) 
51               return a; 
52        else 
53               return c; 
54 }

对这个算法进行分析:

T(1) = 1 

T(N) = 2T(N/2) + O(N) 

最后得出算法的复杂度为:O(NlogN) 

算法四:

下面介绍一个线性的算法,这个算法是许多聪明算法的典型:运行时间是明显的,但是正确性则很不明显(不容易理解)。

 1 //线性的算法O(N) 
 2 long maxSubSum4(const vector<int>& a) 
 3 { 
 4        long maxSum = 0, thisSum = 0; 
 5        for (int j = 0; j < a.size(); j++) 
 6        { 
 7               thisSum += a[j]; 
 8               if (thisSum > maxSum) 
 9                      maxSum = thisSum; 
10               else if (thisSum < 0) 
11                      thisSum = 0; 
12        } 
13        return maxSum; 
14 }

   很容易理解时间界O(N) 是正确的,但是要是弄明白为什么正确就比较费力了。其实这个是算法二的一个改进。分析的时候也是i代表当前序列的起点,j代表当前序列的终点。如果我们不需要知道最佳子序列的位置,那么i就可以优化掉。

    重点的一个思想是:如果a[i]是负数那么它不可能代表最有序列的起点,因为任何包含a[i]的作为起点的子序列都可以通过用a[i+1]作为起点来改进。类似的有,任何的负的子序列不可能是最优子序列的前缀。例如说,循环中我们检测到从a[i]a[j]的子序列是负数,那么我们就可以推进i关键的结论是我们不仅可以把i推进到i+1,而且我们实际可以把它一直推进到j+1

    举例来说,令p是i+1到j之间的任何一个下标,由于前面假设了a[i]+…+a[j]是负数,则开始于下标p的任意子序列都不会大于在下标i并且包含从a[i]到a[p-1]的子序列对应的子序列(j是使得从下标i开始成为负数的第一个下标)。因此,把i推进到j+1是安全的,不会错过最优解。注意的是:虽然,如果有以a[j]结尾的某序列和是负数就表明了这个序列中的任何一个数不可能是与a[j]后面的数形成的最大子序列的开头,但是并不表明a[j]前面的某个序列就不是最大序列,也就是说不能确定最大子序列在a[j]前还是a[j]后,即最大子序列位置不能求出。但是能确保maxSum的值是当前最大的子序列和。这个算法还有一个有点就是,它只对数据进行一次扫描,一旦a[j]被读入处理就不需要再记忆。它是一个联机算法

联机算法:在任意时刻算法都能够对它已读入的数据给出当前数据的解。 

 常量空间线性时间的联机算法几乎是完美的算法。

 

附录:

程序测试:

先通过文件读写函数产生一组随机数并且读入到一个vector<int>中:

 1 //COUNT和MAX_NUM分别表示随机数个数和最大值 
 2 const long COUNT = 1000; 
 3 const int MAX_NUM = 200; 
 4  
 5 //读文件 
 6 bool readFile(vector<int>& input, string fileName) 
 7 { 
 8        ifstream infile(fileName.c_str()); 
 9        if (!infile) 
10               return false; 
11        int s; 
12        while(infile>>s) 
13        { 
14               input.push_back(s); 
15        } 
16        return true; 
17 } 
18  
19 //写大量随机测试数据 
20 bool writeTestData(string fileName) 
21 { 
22        ofstream outfile(fileName.c_str()); 
23        if (!outfile) 
24               return false; 
25        srand((unsigned)time(NULL)); 
26        for (int i = 0; i < COUNT; i++) 
27        { 
28               if (rand() % 2 == 0) 
29                      outfile << rand() % MAX_NUM << '\n'; 
30               else 
31                      outfile << ~(rand() % MAX_NUM) << '\n'; 
32        } 
33        return true; 
34 }

测试可得:

当COUNT = 1000的时候maxSubSum1()要等10s,后三个很快。

当COUNT = 10000的时候maxSubSum2()要等8s,后两个很快。

当COUNT = 1000000的时候maxSubSum3()要等10s,maxSubSum4()要等4s。

其实当COUNT = 1000000这个时候但是作文件读写就要很耗时了,光是in.txt就达到了4.7MB了。

而COUNT = 10000000的时候光是文件读写就要半分钟,in.txt达到了47.2MB,这时候再做maxSubSum3()和maxSubSum4()的比较,maxSubSum4()需要56s,而maxSubSum3()这时候需要85s(包括了读文件的时间)。可见数据量比较大的情况下O(NlogN)的递归算法也是可行的,并不比O(N)低很多。尤其在要求出最大子序列位置的情况下,分治递归算法体现了强大的威力。

  1 程序源码:
  2 
  3 #include <iostream>
  4 
  5 #include <string>
  6 
  7 #include <vector>
  8 
  9 #include <fstream>
 10 
 11 #include <cstdlib>
 12 
 13 #include <ctime>
 14 
 15  
 16 
 17 using namespace std;
 18 
 19  
 20 //COUNT和MAX_NUM分别表示随机数个数和最大值
 21 
 22 const long COUNT = 10000;
 23 
 24 const int MAX_NUM = 200;
 25 
 26  
 27 //读文件
 28 
 29 bool readFile(vector<int>& input, string fileName)
 30 
 31 {
 32 
 33     ifstream infile(fileName.c_str());
 34 
 35     if (!infile)
 36 
 37         return false;
 38 
 39     int s;
 40 
 41     while(infile>>s)
 42 
 43     {
 44 
 45         input.push_back(s);
 46 
 47     }
 48 
 49     return true;
 50 
 51 }
 52 
 53  
 54 //写大量随机测试数据
 55 
 56 bool writeTestData(string fileName)
 57 
 58 {
 59 
 60     ofstream outfile(fileName.c_str());
 61 
 62     if (!outfile)
 63 
 64         return false;
 65 
 66     srand((unsigned)time(NULL));
 67 
 68     for (int i = 0; i < COUNT; i++)
 69 
 70     {
 71 
 72         if (rand() % 2 == 0)
 73 
 74             outfile << rand() % MAX_NUM << '\n';
 75 
 76         else
 77 
 78             outfile << ~(rand() % MAX_NUM) << '\n';
 79 
 80     }
 81 
 82     return true;
 83 
 84 }
 85 
 86  
 87 //穷举法
 88 
 89 long maxSubSum1(const vector<int>& a)
 90 
 91 {
 92 
 93     long maxSum = 0;
 94 
 95     for (int i = 0; i < a.size(); i++)
 96 
 97     {
 98 
 99         for (int j = i; j < a.size(); j++)
100 
101         {
102 
103             long thisSum = 0;
104 
105  
106 
107             for (int k = i; k <= j; k++)
108 
109             {
110 
111                 thisSum += a[k];
112 
113             }
114 
115             if (thisSum > maxSum)
116 
117             maxSum = thisSum;
118 
119         }
120 
121     }
122 
123     return maxSum;
124 
125 }
126 
127  
128 //也是穷举法,不过减去了上面的一些不必要操作O(n^2)
129 
130 long maxSubSum2(const vector<int>& a)
131 
132 {
133 
134     long maxSum = 0;
135 
136     for (int i = 0; i < a.size(); i++)
137 
138     {
139 
140         long thisSum = 0;
141 
142         for (int j = i; j < a.size(); j++)
143 
144         {
145 
146             thisSum += a[j];
147 
148             if (thisSum > maxSum)
149 
150                 maxSum = thisSum;
151 
152         }
153 
154     }
155 
156     return maxSum;
157 
158 }
159 
160  
161 //递归法,复杂度是O(nlogn)
162 
163 long max3(long a, long b, long c)
164 
165 {
166 
167     if (a < b)
168 
169     {
170 
171         a = b;
172 
173     }
174 
175     if (a > c)
176 
177         return a;
178 
179     else
180 
181     return c;
182 
183 }
184 
185  
186 long maxSumRec(const vector<int>& a, int left, int right)
187 
188 {
189 
190     if (left == right)
191 
192     {
193 
194         if (a[left] > 0)
195 
196             return a[left];
197 
198         else
199 
200             return 0;
201 
202     }
203 
204     int center = (left + right) / 2;
205 
206     long maxLeftSum = maxSumRec(a, left, center);
207 
208     long maxRightSum = maxSumRec(a, center+1, right);
209 
210  
211     //求出以左边对后一个数字结尾的序列最大值
212 
213     long maxLeftBorderSum = 0, leftBorderSum = 0;
214     for (int i = center; i >= left; i--)
215     {
216 
217         leftBorderSum += a[i];
218 
219         if (leftBorderSum > maxLeftBorderSum)
220 
221             maxLeftBorderSum = leftBorderSum;
222 
223     }
224 
225  
226     //求出以右边对后一个数字结尾的序列最大值
227 
228     long maxRightBorderSum = 0, rightBorderSum = 0;
229 
230     for (int j = center+1; j <= right; j++)
231 
232     {
233 
234         rightBorderSum += a[j];
235 
236         if (rightBorderSum > maxRightBorderSum)
237 
238             maxRightBorderSum = rightBorderSum;
239 
240     }
241 
242  
243 
244     return max3(maxLeftSum, maxRightSum,
245 
246     maxLeftBorderSum + maxRightBorderSum);
247 
248 }
249 
250  
251 long maxSubSum3(const vector<int>& a)
252 
253 {
254 
255     return maxSumRec(a, 0, a.size()-1);
256 
257 }
258 
259  
260 //线性的算法O(N)
261 
262 long maxSubSum4(const vector<int>& a)
263 
264 {
265 
266     long maxSum = 0, thisSum = 0;
267 
268     for (int j = 0; j < a.size(); j++)
269 
270     {
271 
272         thisSum += a[j];
273 
274         if (thisSum > maxSum)
275 
276             maxSum = thisSum;
277 
278         else if (thisSum < 0)
279 
280             thisSum = 0;
281 
282     }
283 
284     return maxSum;
285 
286 }
287 
288  
289 
290 int main ()
291 
292 {
293 
294     vector<int> input;
295 
296     /**
297 
298     if (!writeTestData("in.txt"))
299 
300     {
301 
302         cout << "写文件错误" << endl;
303 
304     }
305 
306     */
307 
308  
309     if (readFile(input, "in.txt"))
310 
311     {
312 
313         //cout << maxSubSum1(input) << endl;
314 
315         //cout << maxSubSum2(input) << endl;
316 
317         cout << maxSubSum3(input) << endl;
318 
319         cout << maxSubSum4(input) << endl;
320 
321     }
322 
323  
324 
325     return 0;
326 
327 }

 

上一篇:阿里云备案要多久?快速通过阿里云APP进行域名备案方法


下一篇:转]最长递增子序列问题的求解