一、暴力算法 $\mathcal{O}(n^3)$
遍历数组的所有子数组集合，并对其求和，筛选出和的最大值
int maxSumOfSub1(int* array, int length){
int maxSum = 0;
int startIndex = 0, endIndex = 0;
for(int i = 0; i < length; i++){
for(int j = i; j < length; j++){
int sum = 0;
for(int k = i; k <= j; k++)
sum += array[k];
if(maxSum < sum){
maxSum = sum;
startIndex = i;
endIndex = j;
}
}
}
cout << "Begin:" << startIndex << " End:" << endIndex << " Num:" << maxSum << endl;
return maxSum;
}
二、前缀和 $\mathcal{O}(n^2)$
先把数组的前 i 项和求出来并将其保存到数组中，然后计算所有子数组集合的和，筛选其中最大的
int maxSumOfSub2(int* array, int length){
int maxSum = 0;
int sumLen = length + 1;
int sum[sumLen] = {0};
int startIndex = 0, endIndex = 0;
for(int i = 1; i <= length; ++i){
sum[i] = sum[i-1] + array[i-1];
}
// for_each(sum, sum + sumLen, [](int ele){ cout << ele << " ";});
// cout << endl;
for(int i = 0; i < length; i++){
for(int j = i + 1; j <= length; j++){
int res = sum[j] - sum[i];
if(maxSum < res){
maxSum = res;
startIndex = i;
endIndex = j-1;
}
}
}
cout << "Begin:" << startIndex << " End:" << endIndex << " Num:" << maxSum << endl;
return maxSum;
}
三、分治法 $\mathcal{O}(n\log_2{}n)$
先将数组分为两个子数组 a, b；
分别求出两个子数组 a，b 的连续子数组中和的最大值 ma, mb；
还有一种情况：有可能最大和的子数组跨越两个数组 mc；
在计算 mc 时，注意：mc必定包含总区间的中间元素，因此求 mc 等价于从中间元素开始往左累加的最大值 + 从中间元素开始往右累加的最大值。
最后比较 ma, mb, mc，取最大的。
int maxSumOfSub3(int* array, int l, int r){
if(l == r){
return array[l];
}
int mid = (l + r) / 2;
//计算Ma,Mb的情况
int maxa = maxSumOfSub3(array, l, mid);
int maxb = maxSumOfSub3(array, mid + 1, r);
//计算子数组跨越两个子数组（Mc）的情况
int maxc = 0, lmax = 0, rmax = 0, sum = 0;
for(int i = mid; i >= l; i--){//从中间元素开始往左累加的最大值
sum += array[i];
lmax = max(lmax, sum);
}
sum = 0;
for(int i = mid + 1; i <= r; i++){//从中间元素开始往右累加的最大值
sum += array[i];
rmax = max(rmax, sum);
}
maxc = lmax + rmax;
return max(maxc, max(maxa, maxb));
}
四、动态规划法 $\mathcal{O}(n)$
dp[i]表示以下标i指向的元素结尾的所有子数组的和的最大值- 状态转移方程：
dp[i] = max(dp[i-1] + array[i], array[i]) - 最后的子数组最大和：
ans = max(dp[i], ans) - 需要比较三个值，筛选出三者中的最大值：前最大子数组和（索引
i-1之前）、当前项array[i]的值、边界最大子数组和（索引i之前）
int maxSumOfSub4( int* array, int length)
{
int dp[length] = {array[0]};
int maxSum = array[0];
for( int i = 1; i < length; ++i )
{
dp[i] = max(dp[i-1] + array[i], array[i]);
maxSum = max(maxSum, dp[i]);
}
return maxSum;
}
改进一：省去保存历史状态值的数组空间
int maxSumOfSub5( int* array, int length)
{
int boundry = array[0];
int maxSum = array[0];
for( int i = 1; i < length; ++i )
{
boundry = max(boundry + array[i], array[i]);
maxSum = max(maxSum, boundry);
}
return maxSum;
}
改进二：记录最大子数组区间
int maxSumOfSub6( int* array, int length)
{
int dp[length] = {array[0]};
int maxSum = array[0];
int endIndex = 0;
int startIndex = 0;
int tmpBeginIndex = 0;
for( int i = 1; i < length; ++i )
{
// dp[i] = max(dp[i-1] + array[i], array[i]);
// maxSum = max(maxSum, dp[i]);
if(dp[i-1] + array[i] < array[i]){
dp[i] = array[i];
tmpBeginIndex = i;
}
else{
dp[i] = dp[i-1] + array[i];
}
if(maxSum < dp[i]){
maxSum = dp[i];
startIndex = tmpBeginIndex;
endIndex = i;
}
}
cout << "Begin:" << startIndex << " End:" << endIndex << " Num:" << maxSum << endl;
return maxSum;
}
改进三：省去保存历史状态值的数组空间，并且记录大子数组区间
int maxSumOfSub7( int* array, int length)
{
int boundry = array[0];
int maxSum = array[0];
int endIndex = 0;
int startIndex = 0;
int tmpBeginIndex = 0;
for( int i = 1; i < length; ++i )
{
// boundry = max(boundry + array[i], array[i]);
// maxSum = max(maxSum, boundry);
if(boundry + array[i] < array[i]){
boundry = array[i];
tmpBeginIndex = i;
}
else{
boundry += array[i];
}
if(maxSum < boundry){
maxSum = boundry;
startIndex = tmpBeginIndex;
endIndex = i;
}
}
cout << "Begin:" << startIndex << " End:" << endIndex << " Num:" << maxSum << endl;
return maxSum;
}
五、扫描法 $\mathcal{O}(n)$
当加上一个正数时，和会增加；当加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个负数将会减少接下来的和。（与动态规划算法很像似）
int maxSumOfSub8( int* array, int length)
{
int boundry = array[0];
int maxSum = array[0];
int endIndex = 0;
int startIndex = 0;
int tmpBeginIndex = 0;
for( int i = 1; i < length; ++i )
{
if(boundry < 0){
boundry = array[i];
tmpBeginIndex = i;
}
else{
boundry += array[i];
}
if( maxSum < boundry )
{
maxSum = boundry;
startIndex = tmpBeginIndex;
endIndex = i;
}
}
cout << "Begin:" << startIndex << " End:" << endIndex << " Num:" << maxSum << endl;
return maxSum;
}
测试
int main()
{
int a[] = {1,-2,3,10,-4,7,2,-48};
// int a[] = {3,-1,-1,-1,-1,-1,-1,-1};
// int a[] = {-1,-1,-1,-1,-1,-1,-1,3};
// int a[] = {5,-2,-3,-1,-1,-1,-1,-3};
int num = sizeof(a)/sizeof(a[0]);
// int result = maxSumOfSub5(a, num);
int result = 0;
result = maxSumOfSub1(a, num);
result = maxSumOfSub2(a, num);
result = maxSumOfSub3(a, 0, num-1);
cout << "Num:" << result << endl;
result = maxSumOfSub4(a, num);
cout << "Num:" << result << endl;
result = maxSumOfSub5(a, num);
cout << "Num:" << result << endl;
result = maxSumOfSub6(a, num);
result = maxSumOfSub7(a, num);
result = maxSumOfSub8(a, num);
cout << "-----------------------------" << endl;
int b[] = {3,-1,5,-1,9,-20,21,-20,20,21};
num = sizeof(b)/sizeof(b[0]);
result = maxSumOfSub1(b, num);
result = maxSumOfSub2(b, num);
result = maxSumOfSub3(b, 0, num-1);
cout << "Num:" << result << endl;
result = maxSumOfSub4(b, num);
cout << "Num:" << result << endl;
result = maxSumOfSub5(b, num);
cout << "Num:" << result << endl;
result = maxSumOfSub6(b, num);
result = maxSumOfSub7(b, num);
result = maxSumOfSub8(b, num);
return 0;
}
输出：
Begin:2 End:6 Num:18
Begin:2 End:6 Num:18
Num:18
Num:18
Num:18
Begin:2 End:6 Num:18
Begin:2 End:6 Num:18
Begin:2 End:6 Num:18
-----------------------------
Begin:6 End:9 Num:42
Begin:6 End:9 Num:42
Num:42
Num:42
Num:42
Begin:6 End:9 Num:42
Begin:6 End:9 Num:42
Begin:6 End:9 Num:42