1.分而治之发没有看明白
2.第四个算法真的太巧妙了
3.在线处理算法:每得到一个数,终止输入的化都能得到当前状态下的结果
分而治之法C代码
int DivideAndConquer( int List[], int left, int right ) { /* 分治法求List[left]到List[right]的最大子列和 */ int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */ int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/ int LeftBorderSum, RightBorderSum; int center, i; if( left == right ) { /* 递归的终止条件,子列只有1个数字 */ if( List[left] > 0 ) return List[left]; else return 0; } /* 下面是"分"的过程 */ 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; } /* 右边扫描结束 */ /* 下面返回"治"的结果 */ return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum ); } int MaxSubseqSum3( int List[], int N ) { /* 保持与前2种算法相同的函数接口 */ return DivideAndConquer( List, 0, N-1 ); }