基础算法：分治

张开发
• 2026/5/12 20:38:51 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

基础算法：分治
#基础算法问题一分为二 —递归([[DFS]])-合并答案时间优化O(nn)-O(n log n)步骤分折半 min(lr)/2治左右递归 dfs(l,mid),dfs(mid1,r)合跨中界的答案必须线性合并否则白分返max(左右跨中)或累加模板// 最大子段和——分治版简洁注释intdfs(intl,intr){if(lr)returna[l];// 只剩一个元素直接返回intm(lr)1;// 折半intretmax(dfs(l,m),dfs(m1,r));// 左右子问题最优解intsuma[m],lmaxa[m];// 向左延伸的最大后缀和for(intim-1;il;--i)lmaxmax(lmax,suma[i]);suma[m1];intrmaxa[m1];// 向右延伸的最大前缀和for(intim2;ir;i)rmaxmax(rmax,suma[i]);returnmax(ret,lmaxrmax);// 跨中、左、右三者最值}// 逆序对——归并版简洁注释lldfs(intl,intr){if(lr)return0;// 空或单元素逆序对为 0intm(lr)1;ll retdfs(l,m)dfs(m1,r);// 左右子区间逆序对累加// 以下归并两个已排好序的子区间并统计跨越中点的逆序对intil,p1l,p2m1;while(p1mp2r){if(a[p1]a[p2])b[i]a[p1];// 左侧小无逆序对else{retm-p11;// 左侧剩余全都 a[p2]b[i]a[p2];}}while(p1m)b[i]a[p1];// 把剩余元素直接拷完while(p2r)b[i]a[p2];for(intjl;jr;j)a[j]b[j];// 复制回原数组供上层使用returnret;}//时间复杂度On log n

更多文章