算法设计--在数组中找求和最大的连续子串
2021-02-09 07:17
标签：too 数组 ++ 复制 算法 重置 分治算法 复杂度 == 问题：输入具有n个整数的向量arr，输出向量的任意连续子向量和的最大值 特殊情况（1、当向量都为正数时，为整个向量 2、当向量都为负数时，为0，即空子串 ） 1、O（n2）的算法 （循环对所有情况进行遍历） 其中有个小细节就是 注意sum(i, j-1) 和 sum(i, j）的关系，不要每次在求和的时候从头（i的位置）开始，那样会使复杂度变为O(n3) 2、O(nlogn)算法 基于分治原理的算法：首先将n的原问题划分为大小基本相等的两个子问题，我们分别称为a和b子问题，可以递归找出a和b问题的最大子向量，称为maxa 和 maxb。 但他们两个之间的最大值不一定使我们求得n问题的最优解，还有一种可能是跨越a和b的边界，我们称之为c，c情况的最优解为maxc。 那么问题变成了如何求解maxc？ 我们可以发现，maxc中在a的部分为a中包括a的右边界的最大值，maxc中在b的部分为b中包括b的左边界的最大值，因此可以在O(N)的时间内算出maxc 因此得到T(N) = 2T(N/2) + O(N) 推导得到T(N) = O(nlogn) 3、O(n)算法 先上代码，代码非常简短，理解起来比较困难，但是执行效率非常高 假设我们已经解决了x[0,n-1]的问题，利用分治算法的原理：前i个元素中，最大总和子数组要么在前i-1个元素中，要么其结束位置在i处。 分析其结束为止在i处的情况，那么子向量中除去i处的元素组成的子向量一定是x[0,i-1]中结束位置为i-1的最大子向量。 看代码中的关键变量为maxendinghere：在循环语句的第一个赋值语句之前，maxendinghere是结束位置为i-1的最大子向量的和；赋值语句将其修改为结束位置为i的最大子向量的和。若加上x[i]后结果依然为正值，则结束位置在i的最大子向量值就为maxendinghere+x[i],如果为负值，则重置为0。 算法设计--在数组中找求和最大的连续子串 标签：too 数组 ++ 复制 算法 重置 分治算法 复杂度 == 原文地址：https://www.cnblogs.com/ExMan/p/12752651.html
1 #include
1 int find2(int arr[], int s_p, int e_p){
2 int m, sum, i, maxsofar, lmaxsofar, rmaxsofar;
3 maxsofar = 0;
4
5 if(s_p == e_p){
6 return maxsofar;
7 }
8 else if(s_p == e_p){
9 return max(arr[s_p],0);
10 }
11 else{
12 m = (s_p + e_p) / 2;
13
14 lmaxsofar = 0;
15 sum = 0;
16 for(i=m; i>=s_p; i--){
17 sum += arr[i];
18 lmaxsofar = max(sum, lmaxsofar);
19 }
20
21 rmaxsofar = 0;
22 sum = 0;
23 for(i=m+1; i
1 int find3(int arr[], int n){
2 int i,maxsofar,maxendinghere;
3 maxsofar = 0;
4 maxendinghere = 0;
5
6 for(i=0; i
下一篇：机器学习5线性回归算法
文章标题：算法设计--在数组中找求和最大的连续子串
文章链接：http://soscw.com/index.php/essay/52989.html