HDU-1231,最大区间连续和总结-分治法-dp

淩亂°似流年 2021-09-20 09:08 265阅读 0赞

# 1、暴力枚举所有区间的连续和，维护最大和 #

int p1,p2,maxs=-INF;p1=p2=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
                int sum=0;
            for(int k=i;k<=j;k++){
                sum+=a[k];
            }
            if(maxs<sum){maxs=sum;p1=i;p2=j;}
        }
    }

# 2、因为求区间和的时候重复了所以可以用S\[i，j\]=S\[1,j\]-S\[1,i-1\]来避免重复 #

int p1,p2,maxs=-INF;p1=p2=0;
    int S[N];S[0]=0;
    for(int i=1;i<=n;i++){S[i]=S[i-1]+a[i];}
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            sum=S[j]-S[i-1];
            if(maxs<sum){maxs=sum;p1=i;p2=j;}
        }
    }

# 3、分治法 #

分治法要求分而治之再合并；

分：分成三部分最大值，左，右，左and右；

治：左右可以递归求，左and右单独求；

合并：取三者最大值即可；

定义【i，j】表示起点终点都在区间里的最大和

将【i，j】上的最大和转换成max(【i,m】，【m+1，j】，起点在前一个区间，终点在后一个区间的最大和）这三者中的最大值；

其中前两个最大和可以递归实现，第三个定义的最大和一定是从中间向两遍扩大区间的过程中的最大值，可以分别遍历左右区间得到；

int maxsum(int* A, int x, int y){ //返回数组在左闭右开区间[x,y)中的最大连续和
    int v, L, R, maxs;
    if(y - x == 1) return A[x]; //只有一个元素，直接返回
    int m = x + (y-x)/2; //分治第一步：划分成[x, m)和[m, y)
    int maxs = max(maxsum(A, x, m),maxsum(A, m, y)); //分治第二步：递归求解
    int v, L, R;
    v = 0; L = A[m-1]; //分治第三步：合并(1)——从分界点开始往左的最大连续和Lfor(int i = m-1; i >= x; i——) L = max(L, v += A[i]);
    v = 0; R = A[m]; //分治第三步：合并(2)——从分界点开始往右的最大连续和R
    for(int i = m; i < y; i++) R = max(R, v += A[i]);
    return max(maxs, L+R); //把子问题的解与L和R比较
    }

# 4、动态规划法 #

求一个区间最大和，要求每个子区间都取到最大和；满足最优子结构；

子区间求最大和又是 重叠子问题；

所以可以用动态规划求解；

首先如果我们要在O（n）的复杂度里算出来，那状态肯定是1维的即只枚区间的一个端点，那由对称性，起点和终点是同等的，所以方便起见我们要枚举的是区间的终点。

所以定义状态dp\[i\]是以i为区间的右端点的最大和;

先不管起点，如果我们知道了dp\[i-1\],dp\[i\]可以选择跟i-1连起来（连起来就是dp\[i-1\]+a\[i\],不连那就只有自己了a\[i\]），这样根据最大和我们知道“如果队友太坑，就卖了不要”否则就跟上队友；这里如果dp\[i-1\]<0就没必要连了

所以dp\[i\]=max(0,dp\[i-1\])+a\[i\];

然后我们要的答案就从各个终点的dp中选最大值就可以了；

for ( int i = 1 ; i <= n ; i++ )
    {
        last = max(0,last)+a[i];
        ans = max(ans,last);
    }

最后的问题是这样定义状态怎么知道起点呢？

那就要从状态转移方程入手，如果连了i-1那起点相同，如果放弃了，就以自己为起点；

所以这道题可以这样写；

#include<cstdio>
    #include<iostream>
    using namespace std; const int N=1e4+1; const int INF=0x7fffffff; int a[N]; int k; int main(){ 
        //freopen("in.txt","r",stdin);
     while(cin>>k){ if(k==0) break; int last,maxs,p1,p2,start=0;last=maxs=-INF; for(int i=1;i<=k;i++){ 
                scanf("%d",&a[i]); if(last<0){ 
                    last=a[i];
                    start=i; } else last+=a[i]; if(last>maxs){ 
                    p1=start;p2=i;
                    maxs=last; } } if(maxs<0){ printf("0 %d %d\n",a[1],a[k]);} else
            printf("%d %d %d\n",maxs,a[p1],a[p2]); } return 0; }

转载于:https://www.cnblogs.com/alonglyn/p/9953962.html