C++实现的一些算法与数据结构源代码

/* 本题分治优化原理 比如贪心能够优化，是因为贪心着眼于局部的最优策略， 只枚举了极少的局部的情况，所以贪心法有时候不一定对，但是一般效率都还可以 动态规划能够优化，是因为找准了状态之间的转移关系，并且存储了中间的状态， 减少了大量重复求状态的计算，所以动态规划一般效率非常高 为什么这道题目（最大连续子序列和）使用分治能够进行优化， 其实分治本身只是一种策略，告诉我们要如何去枚举，分治本身并不减少枚举的次数 所以分治能够得到正确的解，肯定也是枚举了所有的情况， 那为什么分治就过了所有的点， 也就是对比枚举优化的O(n^2)的算法（也是枚举了所有的情况）， 分治为什么能变成O(nlogn)， O(nlogn)相比于O(n^2)肯定是少枚举了很多情况 而我们的分治算法又是对的， 那说明分治算法少枚举的情况都是一些无关紧要的情况， 现在的问题就是， 分治到底少枚举了哪些情况 也就是为什么分治可以优化 可以从以下两个点来分析 (1)、分治将问题规模变小，将问题的规模变小之后，有些时候需要枚举的情况也会变少， a、假设分治内部用到的算法是O(n^2)，假设n是10，原先的10^2=100>二分后的2*5^2=50 b、假设分治内部用到的算法是O(n)，假设n是10，原先的10>=二分后的2*5 a里面看似减少了枚举情况，其实并没有，因为减少的情况跑到②跨越序列中间：i<=mid<=j<=r 所以分治将问题的规模变小并没有减少枚举的情况 (2)、情况②跨越序列中间的算法是O(n)的算法-->(分治优化的关键) 第二种情况：子序列一定包含mid （转换成）===> 即求出区间[i..mid]的最大值与区间[mid..j]的最大值，将其合并即可 那么我们枚举包含mid的子序列的算法是O(n^2) 枚举变量：起点和终点 枚举范围：起点:i...mid，终点:mid...j 结论： 分治本身不能优化算法， 因为分治还是需要将所有可能的情况枚举出来，选最优解， 而分治真正能够优化算法的是：分治里面应用到的策略 我们在分治的过程中创造了信息 我们在用分治算法的时候，就创造了下面这些信息 子序列的情况只能是这三种情况里面的一种 ①完全处于序列的左半：l<=i<=j<=mid ②跨越序列中间：i<=mid<=j<=r ③完全处于序列的右半：mid<i<=j<=r （所以这题就分成三种情况，情况1和3都是递归子问题， 而情况2，利用分治的信息（包含mid），成功的将枚举O(n^2)的算法优化到了O(n)， 自然就减少了一些不必要的枚举的情况） 强调： 分治能够优化，不在与分治这种策略，而是这种分治策略创造了信息， 让我们可以拿这个信息去优化枚举 我们之前反复强调，优化枚举法，需要就是信息、关系式、等式， 而分治法优化的实质就是分治的过程中给我们创造信息，创造了关系式， 从而减少枚举情况 枚举法能够优化的实质是什么 枚举法能够优化的实质是有信息（关系式、等式、条件）可以让我们减少枚举情况（减少枚举范围、减少枚举变量、减少不必要的枚举） 比如在这个题里面，没有信息，我们通过分治就创造了这些信息，从而通过分治法优化了枚举 分治能够优化枚举的实质是什么 a、分治其实只是一种枚举策略，只能改变枚举的方式，并不能减少枚举的次数 b、分治能够优化枚举，不在于分治这种策略，而是这种分治策略创造了信息（比如本题第二种情况子序列一定包含mid），让我们可以拿这个信息去优化枚举 */ //下面代码是没用好分治创造的信息的分治法代码，只能过两个点 //而用好分治法创造的信息的分治法代码，可以过所有点 #include <iostream> #include <algorithm> using namespace std; int a[200005]; int s[200005]={0}; //分治（二分）求最大连续子序列的和 int find(int l,int r){ if(l==r) return a[l]; int mid=(l+r)/2; //1、计算第二种跨越mid情况的序列的最大和 int maxx=-0x7fffffff; for(int i=l;i<=mid;i++){ for(int j=mid;j<=r;j++){ //2、对每一段进行求和，在这些和里面选出最大的 int sum=s[j]-s[i]+a[i]; if(sum>maxx) maxx=sum; } } //2、比较方式1、2、3的最大值 return max(max(find(l,mid),find(mid+1,r)),maxx); } int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; s[i]=s[i-1]+a[i]; } cout<<find(1,n)<<endl; return 0; }