1.3应用实例：最大子列和问题
//这是一个从Ai到Aj连续的一段子列的和
//对N个整数来说，有很多这样的连续的子列，我们要求的是所有连续子列和里面最大的那个，如果这个和是负数的话，我们最后就返回0作为结束
//方法1：暴力破解；方法2：
//以下是暴力破解算法1：
intMaxSubseqSum1( intA[], intN)
{
intThisSum,MaxSum=0;
inti,j,k;
for( i=0 ; i<N ;i++ ){
//i是子列左端位置
for( j=i ; j<N; j++ ){
//j是子列右端位置
ThisSum=0;//This是从A[i]到A[j]的子列和
for( k=i; k<=j ;k++){
ThisSum+=A[k]; //A[i]一直加到A[j]
}
if(ThisSum>MaxSum);//如果刚得到的这个子列和更大
MaxSum=ThisSum;//则更新结果
}//j循环结束
}//i循环结束
returnMaxSum;
}
//复杂度：T(N) = O(N³)，因为三层嵌套的for循环
//算法2：上面中的k循环其实是没有必要的，属于多余的。我只需要在前面一个j的基础上加一个元素就好了
intMaxSubseqSum1( intA[], intN)
{
intThisSum,MaxSum=0;
inti,j,k;
for( i=0 ; i<N ;i++ ){
//i是子列左端位置
ThisSum=0;//This是从A[i]到A[j]的子列和
for( j=i ; j<N; j++ ){
//j是子列右端位置
ThisSum+=A[j];//对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可
if(ThisSum>MaxSum);//如果刚得到的这个子列和更大
MaxSum=ThisSum;//则更新结果
}//j循环结束
}//i循环结束
returnMaxSum;
}
//复杂度是：T(N) = O(N²)，因为两层嵌套的for循环
//算法3：分而治之：把一个比较大的复杂问题切分成小块，然后分头解决，最后再把结果合并起来，这就是分而治之
//第一步：先"分"，也就是说把数组从中间一分为二(二分法)，然后递归地去解决左右两边的问题
//递归地去解决左边的问题，我们会得到左边的一个最大子列和，同理得到右边的最大子列和
//特殊情况：跨越边界的最大子列和
//第二步：后"合"找到两个最大子列和和这个跨越边界的最大子列和后，最后的结果一定是这三个数中间最大的那一个
#include
intMax3( intA, intB, intC )
{ /* 返回3个整数中的最大值 */
returnA>B?A>C?A : C : B>C?B : C;
}
intDivideAndConquer( intList[], intleft, intright )
{ /* 分治法求List[left]到List[right]的最大子列和 */
intMaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
intMaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/
intLeftBorderSum, RightBorderSum;
intcenter, i;
if( left==right ) { /* 递归的终止条件，子列只有1个数字 */
if( List[left] >0 ) returnList[left];
elsereturn0;
}
/* 下面是"分"的过程 */
center= ( left+right ) /2; /* 找到中分点 */
/* 递归求得两边子列的最大和 */
MaxLeftSum=DivideAndConquer( List, left, center );
MaxRightSum=DivideAndConquer( List, center+1, right );
/* 下面求跨分界线的最大子列和 */
MaxLeftBorderSum=0; LeftBorderSum=0;
for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
LeftBorderSum+=List[i];
if( LeftBorderSum>MaxLeftBorderSum )
MaxLeftBorderSum=LeftBorderSum;
} /* 左边扫描结束 */
MaxRightBorderSum=0; RightBorderSum=0;
for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
RightBorderSum+=List[i];
if( RightBorderSum>MaxRightBorderSum )
MaxRightBorderSum=RightBorderSum;
} /* 右边扫描结束 */
/* 下面返回"治"的结果 */
returnMax3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum+MaxRightBorderSum );
}
intMaxSubseqSum3( intList[], intN )
{ /* 保持与前2种算法相同的函数接口 */
returnDivideAndConquer( List, 0, N-1 );
}
intmain() {
intk;
scanf("%d", &k);
inta[k] = {0};
for (inti=0 ; i<k; i++)
scanf("%d", &a[i]);
printf("%d\n", MaxSubseqSum3(a, k));
return0;
}
当两个复杂度加在一起的时候，我们得到的是比较大的那项，所以我们取O弃N
N/2的k次方=1其实就是2的k次方＝N
每展开一层就多一个cN
不是说4变成了1，而是在求[4，-3，5，-2]这个区间的最大子列和时，要选取[4，-3，5]才能达到最大值
一般地，区间[L，mid]，[mid，R]合并后的最大子列和，等于下面这几种情况的最大值：1、区间[L，mid]的最大子列和2、区间[mid，R]的最大子列和3、区间[L，mid]所有元素的和，加上区间[mid，R]的最大前缀和4、区间[mid，R]所有元素的和，加上区间[L，mid]的最大后缀和
//算法3---分治法
//以下内容来自教案给出的答案
intMax3( intA, intB, intC )
{ /* 返回3个整数中的最大值 */
returnA>B?A>C?A : C : B>C?B : C;
}
intDivideAndConquer( intList[], intleft, intright )
{ /* 分治法求List[left]到List[right]的最大子列和 */
intMaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
intMaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/
intLeftBorderSum, RightBorderSum;
intcenter, i;
if( left==right ) { /* 递归的终止条件，子列只有1个数字 */
if( List[left] >0 ) returnList[left];
elsereturn0;
}
/* 下面是"分"的过程 */
center= ( left+right ) /2; /* 找到中分点 */
/* 递归求得两边子列的最大和 */
MaxLeftSum=DivideAndConquer( List, left, center );
MaxRightSum=DivideAndConquer( List, center+1, right );
/* 下面求跨分界线的最大子列和 */
MaxLeftBorderSum=0; LeftBorderSum=0;
for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
LeftBorderSum+=List[i];
if( LeftBorderSum>MaxLeftBorderSum )
MaxLeftBorderSum=LeftBorderSum;
} /* 左边扫描结束 */
MaxRightBorderSum=0; RightBorderSum=0;
for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
RightBorderSum+=List[i];
if( RightBorderSum>MaxRightBorderSum )
MaxRightBorderSum=RightBorderSum;
} /* 右边扫描结束 */
/* 下面返回"治"的结果 */
returnMax3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum+MaxRightBorderSum );
}
intMaxSubseqSum3( intList[], intN )
{ /* 保持与前2种算法相同的函数接口 */
returnDivideAndConquer( List, 0, N-1 );
}
//算法4：在线处理
//在线处理指的是一组数据。例如[-1,3,-2,4,-6,1,6,-1],我算到第4位数停了下来，返回的数据对于前4位数来说是正确的
//每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都可以正确给出当前的解
intMaxSubseqSum4( intA[],intN )
{
intThisSum,MaxSum;
inti;
ThisSum=MaxSum=0;
for( i=0; i<N; i++ ){
ThisSum+=A[i];//向右累加
if( ThisSum>MaxSum)
MaxSum=ThisSum;//发现更大则更新当前结果
elseif(ThisSum<0)//如果当前子列和为负
ThisSum=0;//则不可能使后面的部分和增大，抛弃之
}
returnMaxSum;
}
//复杂度：T(N) = O(N) 是线性的
//作为运行效率最高的算法，也是有所副作用的，在这里的副作用是：正确性不是特别明显
