#include <stdio.h> int Max3 ( int A, int B, int C ) { return (A > B) ? (A > C ?
A : C) : (B > C ? B : C); } int DivideAndConquer ( int List[], int left, int
right ) { int MaxLeftSum, MaxRightSum; int MaxLeftBorderSum, MaxRightBorderSum;
int LeftBorderSum, RightBorderSum; int center, i; if ( left == right ) { 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
) { return DivideAndConquer ( List, 0, N-1 ); } int main(void) { int K, i; int
a[100000]={0}; scanf_s("%d", &K); for ( i = 0; i < K; i++ ) scanf_s("%d",
&a[i]); while(1); return 0; }
测试数据:4,-3,5,-2,-1,2,6,-2
步骤一:分组
A:4,-3
B:5,-2
C:-1,2
D:6,-2
步骤二:治
A 返回 4
B 返回 5
D 返回 2
C 返回 6
步骤三:求跨越分界线的最大序列值
规则,从分界线开始,分两步操作,一边往左,另一边往右,负数应为零,初始化结果为零,当前值大于结果,则更新结果的值,每次扫描将当前与结果的两值相加
且计算结果为当前值,继续判断,如此类推,直至扫描完毕,返回结果值:

第一次:
E :4,-3,5,-2
F :-1,2,6,-2
结果,E = 6,F = 8

第二次:
G:4,-3,5,-2,-1,2,6,-2
结果,G = 11

最后判断:6 8 11,最大值为 11,返回该值。

以上代码出处为 慕课网 - 数据结构(陈越、何钦铭) ,详细分析为自己笔记

技术
©2019-2020 Toolsou All rights reserved,
java实现抢红包功能2021年2月程序员工资统计,平均15144元可怕的不是堕落,而是清楚自己在堕落java简单的抽奖算法,抽奖DemoPYTHON入门期末复习汇总惹什么猫都别惹熊猫!「功夫熊猫」20年对人类拿下4血软件测试之BUG描述JS 的骚操作程序员因拒绝带电脑回家被开除,获赔 19.4 万元vue组件页面高度根据屏幕大小自适应