递归求最大子串和。递归函数计算三部分的值,左区间最大子串和,右区间最大子串和,中间最大子串和。
左/右区间最大子串和:这两个子串可以再分别看出两个需要计算最大子串和的串,再进行递归分为左/右区间,直到左区间只剩下一个数,右区间也只剩下一个数的时候 此时为 a b,返回结果从 左最大子串和a ,右最大子串和b,和中间最大子串和(三种可能a、b、a+b),取最大值。而此时的返回值又会作为上一层递归的左/右区间的最大子串和,然后再进行比较,留下较大的值并且返回。如此循环直到最开始的那一层,找到最大子串和。
中间最大子串和:假设数据为a b c d e f,由于子串的连贯性,分别从c、d开始分别向左、右查找,直到区间端点,求左右的最大子串和相加后返回即可。
#include<stdio.h> int max(int *a,int b,int c); int find(int *a,int l,int r); int main(){ int a[1000],m,n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&a[i]); printf("%d",find(a,0,n-1)); return 0; } int max(int a,int b,int c){ if(a>b){ if(a>c) return a; else return c; } else{ if(c>b) return c; else return b; } } int find(int *a,int l,int r){ if(l==r){ if(a[l]>0) return a[l]; else return 0; } else{ int mid=(l+r)/2,sum=0,max_l=a[l],max_r=a[mid+1],tem=0; for(int i=mid;i>=l;i--){ sum+=a[i]; if(sum>max_l) max_l=sum; } sum=0; for(int i=mid+1;i<=r;i++){ sum+=a[i]; if(sum>max_r) max_r=sum; } sum=max_l+max_r; max_r=find(a,mid+1,r); max_l=find(a,l,mid); return max(sum,max_r,max_l); } }