分治算法把序列分成左右两半递归求解最大连续和合并结果得到序列最大连续和动态规划根据已求出之前序列最大连续和确定当前序列最大连续和从左至右递推代码很容易理解,一看就懂这里就不多说了C代码#includeiostream#includevector#includerandomusingnamespacestd;structResult{size_t left_max_sum_end;//第一个元素是左半部分序列第一元素的左半部分序列最大连续和的最后一个元素在左半部分的索引intleft_max_sum;//左半部分最大连续和size_t right_max_sum_start;//最后一个元素是右半部分序列最后一个元素的右半部分序列最大连续和的第一个元素在右半部分的索引intright_max_sum;//右半部分最大连续和size_t max_sum_start;//当前序列最大连续和序列的起始索引size_t max_sum_end;//当前序列最大连续和序列的终止索引intmax_sum;//当前序列最大连续和intarray_sum;//当前序列元素总和Result(size_t left_max_sum_end,intleft_max_sum,size_t right_max_sum_start,intright_max_sum,size_t max_sum_start,size_t max_sum_end,intmax_sum,intarray_sum):left_max_sum_end(left_max_sum_end),left_max_sum(left_max_sum),right_max_sum_start(right_max_sum_start),right_max_sum(right_max_sum),max_sum_start(max_sum_start),max_sum_end(max_sum_end),max_sum(max_sum),array_sum(array_sum){}};ResultdoMaxConsecutiveSum(vectorintseq,size_t left,size_t right){if(leftright){returnResult(right,seq[left],left,seq[left],left,right,seq[left],seq[left]);}size_t mid(leftright)/2;Result left_resultdoMaxConsecutiveSum(seq,left,mid);Result right_resultdoMaxConsecutiveSum(seq,mid1,right);size_t left_max_sum_endleft_result.left_max_sum_end;intleft_max_sumleft_result.left_max_sum;if(left_max_sumleft_result.array_sumright_result.left_max_sum){left_max_sum_endright_result.left_max_sum_end;left_max_sumleft_result.array_sumright_result.left_max_sum;}size_t right_max_sum_startright_result.right_max_sum_start;intright_max_sumright_result.right_max_sum;if(right_max_sumright_result.array_sumleft_result.right_max_sum){right_max_sum_startleft_result.right_max_sum_start;right_max_sumright_result.array_sumleft_result.right_max_sum;}size_t max_sum_startleft_result.max_sum_start;size_t max_sum_endleft_result.max_sum_end;intmax_sumleft_result.max_sum;if(max_sumright_result.max_sum){max_sum_startright_result.max_sum_start;max_sum_endright_result.max_sum_end;max_sumright_result.max_sum;}if(max_sumleft_result.right_max_sumright_result.left_max_sum){max_sum_startleft_result.right_max_sum_start;max_sum_endright_result.left_max_sum_end;max_sumleft_result.right_max_sumright_result.left_max_sum;}intarray_sumleft_result.array_sumright_result.array_sum;returnResult(left_max_sum_end,left_max_sum,right_max_sum_start,right_max_sum,max_sum_start,max_sum_end,max_sum,array_sum);}intmain(){constintN100;for(inti1;iN;i){intkirand()%i;vectorintseq(ik,0);for(intj0;ji;j){seq[j]j1;}for(intji;jik;j){seq[j]-(rand()%i);}shuffle(seq.begin(),seq.end(),default_random_engine());Result rdoMaxConsecutiveSum(seq,0,seq.size()-1);intmax_sumseq[0];intleft_sumseq[0];size_t max_sum_start0;size_t max_sum_end0;size_t left_sum_start0;for(size_t i1;iseq.size();i)//动态规划求最大连续和{if(left_sum0){left_sum_starti;left_sumseq[i];}else{left_sumseq[i];}if(max_sumleft_sum){max_sum_endi;max_sum_startleft_sum_start;max_sumleft_sum;}}if(max_sum!r.max_sum){cout最大连续和计算错误!endl;exit(-1);}cout最大连续和计算正确endl;cout最大连续和为max_sumendl;cout分治法得出最大连续和下标范围从r.max_sum_start到r.max_sum_end对应;for(size_t runr.max_sum_start;runr.max_sum_end;run){coutseq[run] ;}coutendl;cout动态规划得出最大连续和下标范围从max_sum_start到max_sum_end对应;for(size_t runmax_sum_start;runmax_sum_end;run){coutseq[run] ;}coutendl;}//shuffle(seq.begin(), seq.end(), default_random_engine());/*vectorint seq(N, 0); for (int i 0; i N; i) { seq[i] i 1; } Result r doMaxConsecutiveSum(seq, 0, seq.size() - 1); int max_sum seq[0]; int left_sum seq[0]; size_t max_sum_start 0; size_t max_sum_end 0; size_t left_sum_start 0; for (size_t i 1; i seq.size(); i) { if (left_sum 0) { left_sum_start i; left_sum seq[i]; } else { left_sum seq[i]; } if (max_sum left_sum) { max_sum_end i; max_sum_start left_sum_start; max_sum left_sum; } } if (max_sum ! r.max_sum) { cout 最大连续和计算错误! endl; exit(-1); } cout 最大连续和计算正确 endl; cout 最大连续和为 max_sum endl; cout 分治法得出最大连续和下标范围从 r.max_sum_start 到 r.max_sum_end 对应; for (size_t run r.max_sum_start; run r.max_sum_end; run) { cout seq[run] ; } cout endl; cout 动态规划得出最大连续和下标范围从 max_sum_start 到 max_sum_end 对应; for (size_t run max_sum_start; run max_sum_end; run) { cout seq[run] ; } cout endl;*/return0;}