求连续子向量的最大和
本问题来自于《编程珠玑》第八章。
问题：输入是具有n个整数的向量，输出是输入向量的任何连续子向量中的最大和。
算法一
立方算法，该算法需求出所有子序列的和，时间复杂度为$O(n^3)$。本算法对$max$进行了$n^3/2$次调用。
int maxSum1(vector<int> nums) {
int maxsofar = 0, len = nums.size();
if(len == 0) {
return 0;
} else if(len > 0) {
for(int i=0; i<len; i++) {
for(int j=i; j<len; j++) {
int sum = 0;
for(int k=i; k<=j; k++) {
sum += nums[k];
}
maxsofar = max(maxsofar, sum); //求出所有子序列的和
}
}
if(maxsofar > 0) {
return maxsofar;
} else {
return 0;
}
}
}
算法二
算法二都是通过固定的步数而不是算法一的$[j-i+1]$步内完成对$nums[i,j]$的求和，但根据在固定时间内计算总和时使用方法的不同分为了a、b两种算法，两者的时间复杂度都为$O(n^2)$。本算法对$max$进行了$n^2/2$次调用。
a算法由$nums[i,j]$的总和与前面计算出的总和$nums[i,j-1]$密切相关可得。
int maxSum2a(vector<int> nums) {
int maxsofar = 0, len = nums.size();
if(len == 0) {
return 0;
} else if(len > 0) {
for(int i=0; i<len; i++) {
int sum = 0;
for(int j=i; j<len; j++) {
sum += nums[j];
maxsofar = max(maxsofar, sum);
}
}
if(maxsofar > 0) {
return maxsofar;
} else {
return 0;
}
}
}
b算法是通过访问在循环执行前就已构建的数据结构来计算综合。cumarr中的第i个元素包含$nums[0,i]$中各个数的累加和，所以$nums[i,j]$中各个数的和可由$cumarr[j]-cumarr[i-1]$得到。
int maxSum2b(vector<int> nums) {
int maxsofar = 0, len = nums.size();
int cumarr[len];
if(len == 0) {
return 0;
} else if (len > 0) {
cumarr[-1] = 0;
for(int i=0; i<len; i++) {
cumarr[i] = cumarr[i-1] + nums[i];
}
for(int i=0; i<len; i++) {
for(int j=i; j<len; j++) {
int sum = cumarr[j] - cumarr[i-1];
maxsofar = max(maxsofar, sum);
}
}
if(maxsofar > 0) {
return maxsofar;
} else {
return 0;
}
}
}
算法三
采用分治算法，将输入向量分为左、右两部分，分别计算左、右半部分的子序列和，再加上横跨左右两部分的最大连续子序列和，最后返回三个和中的最大值，该算法的时间复杂度为$O(nlogn)$。 本算法使用了对数的额外空间，其他算法仅使用了常熟的额外空间。
注：开始的时候以为for循环里只是求出了半截子序列的所有和，并没有对子序列里的任意连续子序列求和，仔细研读书本后，发现了是在return里的maxSum3里实现了递归。
int maxSum3(vector<int> nums, int l, int u) {
if(l > u) {
return 0;
}
if(l == u) {
return max(0, nums[1]);
}
int m = (l + u) / 2;
int sum = 0;
int lmax = sum;
for(int i=m; i>=1; i--) {
sum += nums[i];
lmax = max(lmax, sum);
}
sum = 0;
int rmax = sum;
for(int j=m+1; j<u; j++) {
sum += nums[j];
rmax = max(rmax, sum);
}
return (lmax+rmax >= maxSum3(nums, 1, m)) ? (lmax+rmax >= maxSum3(nums, m+1, u)
? lmax+rmax : maxSum3(nums, m+1, u))
: (maxSum3(nums, 1, m) >= maxSum3(nums, m+1, u)
? maxSum3(nums, 1, m) : maxSum3(nums, m+1, u));
}
算法四
该算法为扫描算法，从数组最左端开始扫描，一直到最右端，记下遇到的子序列的和的最大值。最大和的最大值为0，假设我们已经解决了$nums[0,i-1]$的问题，此处可以采用类似于分治法的思路，前i个元素中，子序列最大和要么在前$i-1$个元素中（我们将其存储在子啊$maxsofar$中），要么在其结束位置i处（我们将其存储在$maxendinghere$中），该算法的时间复杂度为$O(n)$。本算法对$max$进行了$2n$次调用，是实时的，一趟输入完毕它就计算出答案，也别适用于处理磁盘文件。
int maxSum4(vector<int> nums) {
int maxsofar = 0, maxendinghere = 0, len = nums.size();
if(len == 0) {
return 0;
} else if(len > 0) {
for(int i=0; i<len; i++) {
maxendinghere = max(maxendinghere+nums[i], 0);
maxsofar = max(maxsofar, maxendinghere);
}
return maxsofar;
}
}