发现这个文章写的很好，所以转载了，文章来源：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 }
