甘肃省建设厅官方网站张睿,做网站比特币钱包,网站开发小组,产品图册设计公司1. 描述最大字段和的分治算法
题目 思路
判断最大子段和#xff0c;可以用分治的思想#xff0c;每次将序列一分为二#xff0c;选择两个序列的最大子段和。
但是这里还有一种可能#xff0c;就是子段可以横跨两个子序列#xff0c;所以我们的最大子段和就是#xff1…1. 描述最大字段和的分治算法
题目 思路
判断最大子段和可以用分治的思想每次将序列一分为二选择两个序列的最大子段和。
但是这里还有一种可能就是子段可以横跨两个子序列所以我们的最大子段和就是
MAX左边序列最大字段和横跨两序列的最大子段和右边序列的最大子段和。
对于左右两边的最大子段和可以用分治递归的方法来做临界条件就是序列中只剩一个数了这时候最大子段和就是这个数而递归函数就是对左右两边分别求最大子段和调用自身而且还得求跨序列的最大子段和取三者的最大值来返回。
那么怎么求跨序列的最大子段和呢其实很简单首先要对原来的大序列添加几个指针开头的是指针l最右边的是指针r因为要分治所以再设置一个中间的指针mid此时序列就可以分为两个部分分别是lmid和mid1r这时候的跨序列子段必须包含mid和mid1这两个地方当然也可以向左或向右延申所以我们只需要求出从mid开始向左延申的最大字段和还有从mid1开始向右延申的最大子段和将两者相加就能得到跨序列的最大子段和了。
思路很好理解照着上面的描述画出图来就一目了然了。下面来看看代码实现吧。
代码
#includebits/stdc.h
using namespace std;
const int N 1e5;
int n, a[N];
int maxSum (int left, int right) {if (left right)return a[left];int mid left right 1;int lmax maxSum (left, mid);int rmax maxSum (mid 1, right);int sum a[mid];int clmax a[mid];for (int i mid - 1; i left; i--) {sum a[i];if (sum clmax)clmax sum;}sum a[mid 1];int crmax a[mid 1];for (int i mid 2; i right; i) {sum a[i];if (sum crmax)crmax sum;}int cmax clmax crmax;int maxsum max (cmax, max (lmax, rmax));if (maxsum 0)maxsum 0;return maxsum;
}
int main () {cin n;for (int i 0; i n; i)cin a[i];cout maxSum (0, n - 1);return 0;
} 2. 分析该算法的时间复杂度
分解子问题O(1)
求解子问题2T(n/2)
合并子问题O(n)
故时间复杂度为T(n)2T(n/2)O(n)nlogn 3. 对分治法的体会和思考
分治法的设计思想是将一个难以直接解决的大问题分割成一些规模较小的相同问题以便各个击破分而治之。
其中的划分再击破和递归的分解再解决异曲同工其实同样用到了递归的思想只不过分治法先分再治最后还得合并。
