最大子串
在一个数字序列中,找到一个子串序列,使得这个子串各个数字的和最大
做法如下:
- 暴力
- 分治
瞎搞线性遍历
暴力就不说了
分治这个做法在算导里讲得十分详细,取mid为序列的中间位置,则这个子串在序列中有三种情况:
- 子串在mid左边
- 子串在mid右边
- 子串横跨了mid
对于1、2两种情况,可以直接递归继续二分讨论这三种情况,直到二分到只剩下一个值,此时直接返回该值的左右位置下标(其实是同一个下标),和它的值。
对于第3种情况,也不麻烦,只需要对当前区间来一遍遍历即可讨论出这种情况。
最后对三种情况取一个最大值回溯就行了。
由于这个分治策略属于一种二分,所以该分治树有logN层高,每层都只有第三种情况遍历了N个值,故时间复杂度为O(nlogn)
实现起来也脉络清晰明了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
#include <cstdio> #include <iostream> using namespace std; const int _maxn=100010,inf=2100000000; struct e{ int l,r,sum; //重定义 >= bool operator >= (e y){ return sum>=y.sum; } }ans; int a[_maxn]; //对第3种情况的遍历 e calc(int l,int mid,int r){ e b; int sum,min_left,max_right; int l_sum,r_sum; //从中间往两边遍历 l_sum=-inf; sum=0; for(int i=mid;i>=l;i--){ sum+=a[i]; if(sum>l_sum){ l_sum=sum; min_left=i; } } r_sum=-inf; sum=0; for(int i=mid+1;i<=r;i++){ sum+=a[i]; if(sum>r_sum){ r_sum=sum; max_right=i; } } b.l=min_left; b.r=max_right; b.sum=l_sum+r_sum; return b; } e find(int l,int r){ if(l==r){ e b; b.l=l; b.r=r; b.sum=a[l]; return b; } else{ e bl,br,bc; int mid=(l+r)>>1; bl=find(l,mid); //第一种情况 br=find(mid+1,r); //第二种情况 bc=calc(l,mid,r); //第三种情况 //三种情况取最大值 if(bl>=bc && bl>=br) return bl; else if(br>=bl && br>=bc) return br; else return bc; } } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); ans=find(1,n); printf("%d->%d=%d\n",ans.l,ans.r,ans.sum); return 0; } |
假如当前有一子串是sum[i,j]=a[i]->a[j],那么对于a[j+1]就有两种情况(不考虑a[j+1]=0):
- a[j+1]>0,则sum[i,j+1]一定比sum[i,j]大,此时可以更新最优解
- a[j+1]<0,则sum[i,j+1]一定比sum[i,j]小,直接接纳a[j+1]
但是万一a[j+1]一直过了很久才出现正数怎么办?也许出现正数以后就不再有负数那又要怎么更新?
于是就可以规定,当sum[i,j]<0时,就从零再来
因为当sum[i,j]<0,那么从a[j]以前的和对a[j+1]以后的数字都是没有贡献的:
- 显而易见,当i<=m<=j时,总有sum[m,j]<0
所以此时,我们就应该从零再来累计了
这样,实现起来就轻松多了,没有任何累赘,每个数字只需要判断一次,时间复杂度是O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
//此代码不太适用于有零的情况,仅供参考 #include <iostream> #include <cstdio> using namespace std; int main(){ int x,n,sum=0,left=1,ansleft,ansright,ans=-2100000000; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&x); sum+=x; if(sum<0){ sum=0; left=i+1; continue; } if(sum>ans){ ansleft=left; ansright=i; ans=sum; } } printf("%d->%d=%d\n",ansleft,ansright,ans); return 0; } |
代码未经过题目的洗礼,错了不怪我 ( 逃
-- 热度:1,906 ℃
-- 于 ,共写了750个字;
-- 文内使用到的标签:
-- 于 ,共写了750个字;
-- 文内使用到的标签:
wordpress看着也不错
嗯,typecho功能有点少