精华内容
下载资源
问答
  • purplest ...最大连续区间和的算法总结 最大连续区间和是一个经典的问题。给定一个长度为n的序列a[1],a[2]...a[n-1],a[n],求一个连续的子序列a[i],a[i+1]...a[j-1],a[j],使得a[i]+a[i+1]......

    转载自:http://www.cppblog.com/purplest/archive/2013/03/04/198199.html

    purplest

    最大连续区间和是一个经典的问题。给定一个长度为n的序列a[1],a[2]...a[n-1],a[n],求一个连续的子序列a[i],a[i+1]...a[j-1],a[j],使得a[i]+a[i+1]...a[j-1]+a[j]最大。

    ①最简单最容易想到的就是根据定义来枚举。
    枚举上下界{i,j | 0<=i<=j<=n},维护一个max值即可。
    其中枚举上下界的时间复杂度为O(n^2),求区间和的复杂度为O(n),所以总时间复杂度为O(n^3)。

    for ( int i = 1 ; i <= n ; i++ )
         for ( int j = i ; j <= n ; j++ )
             ans = max(ans,accumulate(a+i,a+j+1,0));


    ②其实就是第一种方法的优化。
    这里有个很容易想到的优化,即预处理出前缀和sum[i]=a[0]+a[1]+...+a[i-1]+a[i],算区间和的时候即可将求区间和的复杂度降到O(1),枚举上下界的复杂度不变,所以总时间复杂度为O(n^2)。

     

    for ( int i = 1 ; i <= n ; i++ )
         sum[i]=sum[i-1]+a[i];
     for ( int i = 1 ; i <= n ; i++ )
         for ( int j = i ; j <= n ; j++ )
             ans = max(ans,sum[j]-sum[i-1]);


    ③可以利用动态规划的思维来继续优化,得到一个线性的算法,也是最大连续区间和的标准算法
    定义maxn[i]为以i为结尾的最大连续和,则很容易找到递推关系:maxn[i]=max{0,maxn[i-1]}+a[i]。
    所以只需要扫描一遍即可,总时间复杂度为O(n)。

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


    ④同样用到类似的思维。
    首先也需要预处理出前缀和sum[i],可以推出ans=max{sum[i]-min{sum[j] } | 0<=j<i<=n }。
    而最小前缀和可以动态维护,所以总时间复杂度为O(n)。

    for ( int i = 1 ; i <= n ; i++ )
         sum[i]=sum[i-1]+a[i];
     for ( int i = 1 ; i <= n ; i++ )
     {
         ans = max(ans,sum[i]-minn);
         minn = min(minn,sum[i]);
     }


    总结:虽然朴素的O(n^3)和前缀和优化的O(n^2)算法很容易想到,但代码实现却反而比方法三麻烦,第四个方法虽然有和方法三相同的复杂度,但需要一个预处理和多出的O(n)的空间,所以,方法三很好很强大。

     

    转载于:https://www.cnblogs.com/yfs123456/p/5741832.html

    展开全文
  • 最大连续区间和是一个经典问题。给定一个长度为n序列a[1],a[2]...a[n-1],a[n],求一个连续子序列a[i],a[i+1]...a[j-1],a[j],使得a[i]+a[i+1]...a[j-1]+a[j]最大。①最简单最容易想到就是根据定义来枚举。...

    最大连续区间和是一个经典的问题。给定一个长度为n的序列a[1],a[2]...a[n-1],a[n],求一个连续的子序列a[i],a[i+1]...a[j-1],a[j],使得a[i]+a[i+1]...a[j-1]+a[j]最大。

    ①最简单最容易想到的就是根据定义来枚举。
    枚举上下界{i,j | 0<=i<=j<=n},维护一个max值即可。
    其中枚举上下界的时间复杂度为O(n^2),求区间和的复杂度为O(n),所以总时间复杂度为O(n^3)。

    for ( int i = 1 ; i <= n ; i++ )
        for ( int j = i ; j <= n ; j++ )
            ans = max(ans,accumulate(a+i,a+j+1,0));


    ②其实就是第一种方法的优化。
    这里有个很容易想到的优化,即预处理出前缀和sum[i]=a[0]+a[1]+...+a[i-1]+a[i],算区间和的时候即可将求区间和的复杂度降到O(1),枚举上下界的复杂度不变,所以总时间复杂度为O(n^2)。

    for ( int i = 1 ; i <= n ; i++ )
        sum[i]=sum[i-1]+a[i];
    for ( int i = 1 ; i <= n ; i++ )
        for ( int j = i ; j <= n ; j++ )
            ans = max(ans,sum[j]-sum[i-1]);


    ③可以利用动态规划的思维来继续优化,得到一个线性的算法,也是最大连续区间和的标准算法
    定义maxn[i]为以i为结尾的最大连续和,则很容易找到递推关系:maxn[i]=max{0,maxn[i-1]}+a[i]。
    所以只需要扫描一遍即可,总时间复杂度为O(n)。

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


    ④同样用到类似的思维。
    首先也需要预处理出前缀和sum[i],可以推出ans=max{sum[i]-min{sum[j] } | 0<=j<i<=n }。
    而最小前缀和可以动态维护,所以总时间复杂度为O(n)。

    for ( int i = 1 ; i <= n ; i++ )
        sum[i]=sum[i-1]+a[i];
    for ( int i = 1 ; i <= n ; i++ )
    {
        ans = max(ans,sum[i]-minn);
        minn = min(minn,sum[i]);
    }


    总结:虽然朴素的O(n^3)和前缀和优化的O(n^2)算法很容易想到,但代码实现却反而比方法三麻烦,第四个方法虽然有和方法三相同的复杂度,但需要一个预处理和多出的O(n)的空间,所以,方法三很好很强大。

    转载于:https://www.cnblogs.com/cdyboke/p/4975852.html

    展开全文
  • 最大连续区间和算法详解+代码

    千次阅读 2018-06-07 14:06:58
    本篇主要记录了最大连续区间和的暴力算法和dp算法(三种写法) 以及讲解了求最大区间和的区间左右下标的方法 ----------------------------------------------------------------------------------- 问题概述 ...

    写在前边

    本篇主要记录了最大连续区间和的暴力算法和dp算法(三种写法)

    以及讲解了求最大区间和的区间左右下标的方法

    -----------------------------------------------------------------------------------

    问题概述

    这是一个经典的问题。

    给定一个长度为n的序列a[1],a[2]...a[n-1],a[n]

    求一个连续的子序列 a[i],a[i+1]...a[j-1],a[j],使得a[i]+a[i+1]...a[j-1]+a[j]最大。

    暴力枚举法  O(n^2)

    我们要求最大的连续区间和,

    首先我们知道预处理出前缀和数组可以方便的求出区间和

    那么我们再暴力枚举区间左右边界  找出最大的那个区间和就好了

    这个暴力的做法很好想

            int n;
    	scanf("%d",&n);
    	for(int i=1;i<=n;i++){
                scanf("%d",&a[i]);
    	}
    	for(int i=1;i<=n;i++){//预处理前缀和数组
                sum[i]=sum[i-1]+a[i];
    	}
    	int flag,ans=0;
    	for(int i=1;i<=n;i++){//暴力枚举左右边界
                for(int j=i;j<=n;j++){
                    ans=ans>(sum[j]-sum[i-1])?ans:(sum[j]-sum[i-1]);//记录最大值
                }
    	}
    	printf("%d",ans);

    显然 这个n^2的方法不够优秀  难以解决数量较大的数据

    所以我们需要进一步优化

    动态规划解法  复杂度O(n)     ---------- (三种写法)

    我们让dp[ i ]等于 以a[ i ]为结束的 最大连续子段和

    因为是以a[ i ]为结束且是连续子段  那么

    dp[ i ] 要么就是  a[ i ]本身

              要么 就是a[ i ] + 以a[ i-1 ]为结束的最大连续字段和  也就是 a[ i ] + dp[ i - 1 ]

    所以 状态转移方程出来了      dp[i] = max( A[i], dp[i-1]+A[i] )

    代码

    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+7;
    ll a[maxn];
    ll dp[maxn];
    const ll INF=8e18;
    ll n,num,x;
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%lld",&a[i]);//输入
        dp[0]=0;
        for(int i=1;i<=n;i++){//状态转移方程
            dp[i]=max(a[i],dp[i-1]+a[i]);
        }
        ll maxn=0;
        for(int i=1;i<=n;i++){//遍历找最大值
            maxn=max(dp[i],maxn);
        }
        printf("%lld\n",maxn);
    }
    

    优化常数

    这个O(n)的算法  其实仔细算的话(加上输入)  是O(3n)

    我们其实可以优化一下常数

    输入和记录dp数组以及记录最大值都可以在一遍内完成

    这个dp数组  也可以发现  扫描一遍 保留最大值就好了  那么数组也省了  一个变量就够了

    最终这个写法也是求解最大连续区间和的标准解法  代码如下

    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+7;
    ll a[maxn];
    ll n,ans,dp;
    int main(){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            dp=max(a[i],dp+a[i]);
            ans=max(dp,ans);
        }
        printf("%lld\n",ans);
    }
    

     还有另一种写法 也是dp的思想   复杂度O(n)

    我们预处理出前缀和数组  那么sum[j]-sum[i]就是一段区间的和了

    那么我们很容易得到  ans = max {  sum[ j ] - min {  sum[ i ]  }  }  ( j > i )

    我们只要用一个变量 动态维护一个最小前缀和就好了 

    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+7;
    ll a[maxn],sum[maxn];
    ll n,ans,minn;
    int main(){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            sum[i]=sum[i-1]+a[i];//统计前缀和数组
            ans=max(sum[i]-minn,ans);//动态维护最大区间和
            minn=min(minn,sum[i]);//动态维护最小前缀和
        }
        printf("%lld\n",ans);
    }

    打印最大区间和的左右下标

    例题:hdu1003

    链接   传送门

    这个题呢   求最大连续区间和  并且打印出来那个区间的左右边界下标

    其实呢  很好写  把前边求最大区间和的算法 稍作改动就好了

    优化过常数之后的动态规划解法是这样写的

    核心的两句就是

      dp=max(a[i],dp+a[i]);
      ans=max(dp,ans);

    这两句其实可以用if else语句来写

    if(dp>0) dp=dp+a[i];
    else dp=a[i];
    
    if(ans>dp)ans=dp
    else  ans=ans;

    那么这下就很好看出了

    那么我们在适当的地方记录下下标就好了

    s e  //s为区间左端点  e为区间右端点
    t    //t为中间变量  用来存储改变后的区间左端点
    
    int ans=-INF,dp=0,t=1,s=1,e=1;
    if(dp>0){
        dp=dp+a[i];
    } 
    else{
        dp=a[i];t=i;
    } 
    if(ans>dp){
        ans=dp;
        s=t;e=i
    }

     

    hdu1003   AC代码

    #include<stdio.h>
    #include<iostream>
    #include<algorithm>
    #include<string.h>
    using namespace std;
    const int INF=0x3f3f3f3f;
    int n,T,num,x;
    int main(){
        scanf("%d",&T);
        while(T--){
            num++;
            scanf("%d",&n);
            int ans=-INF,dp=0,t=1,e=1,s=1;
            for(int i=1;i<=n;i++){
                scanf("%d",&x);
                if(dp>=0) dp+=x;
                else dp=x,t=i;
                if(dp>ans){
                    ans=dp;s=t;e=i;
                }
            }
            cout<<"Case "<<num<<":"<<endl;
            cout<<ans<<" "<<s<<" "<<e<<endl;
            if(T!=0)cout<<endl;
        }
    }
    

     

     

     

     

     

     

    展开全文
  • 最大连续区间和问题

    2017-08-27 16:40:00
    2017-08-2716:38:47 writer:pprp 最大连续区间和,可以有很多种方法实现,...@theme:最大连续区间和的算法 @writer:pprp @declare:有几种方法 @date:2017/8/27 */ #include <bits/stdc++.h> u...

    2017-08-27 16:38:47

    writer:pprp

    最大连续区间和,可以有很多种方法实现,其中最常见的是运用一维前缀和还有动态规划来解决的;

    代码如下:

    /*
    @theme:最大连续区间和的算法
    @writer:pprp
    @declare:有几种方法
    @date:2017/8/27
    */
    
    #include <bits/stdc++.h>
    
    using namespace std;
    const int maxn = 10000;
    int a[maxn];
    int sum[maxn];
    int ans;
    
    int main()
    {
        //法一、暴力解,这就不写了
        //法二、采用一维前缀和
    
        ios::sync_with_stdio(false);
        int N;
        cin >> N;
        for(int i = 0 ; i < N ; i++)
        {
            cin >> a[i];
        }
        sum[0] = a[0];
        for(int i = 1 ; i < N ; i++)
            sum[i] = sum[i-1] + a[i];
    
        ans = 0;
        for(int i = 0 ; i < N ; i++)
            for(int j = i+1 ; j < N ; j++)
                ans = max(ans,sum[j]-sum[i-1]);
                
                cout << ans << endl;
        //法三、动态规划
        int ans = 0;
        int tmp = 0;
        for(int i = 0 ; i < N ; i++)
        {
              tmp = max(tmp,0) + a[i];
              ans = max(ans, tmp);
        }
        
        cout << ans << endl;
        //总结,一般都采用的是第三种方法,比较省时间和空间
        return 0;
    }

     

    转载于:https://www.cnblogs.com/pprp/p/7440729.html

    展开全文
  • 1.输出数组最大连续区间的和 动态规划: 设f(i) 为长度i的最大连续区间的和。 则有 f(i) = f(i-1) +a(i) 如果f(i-1)>0 f(i) = a(i) 如果f(i-1)<0 依次从小大求解f(i)最大值 int nCurSum = 0; int ...
  • 今天做了一个程序,是实现结对编程小项目,项目是寻找一组数组中最大的一组子数组(条件是数组必须连续)。通过我们模拟一组数据: 例如:inta[]={9,8,-5,4,3}  首先是选定一个初始值假如是a[0],则第二个数是a...
  • 最大连续和-高效算法

    2019-02-19 20:24:42
    求一个序列的最大连续区间和(有负数),可以前缀和,但是复杂度高。下面是复杂度为O(n)高效算法。紫书P224,详情见代码注释。 #include&amp;lt;iostream&amp;gt; #include&amp;lt;cstdio&amp;...
  • 贪心算法-求区间至少连续k的最大和

    千次阅读 2013-04-14 16:59:53
    题意:对于一个整数n,表示该区间整数个数,求至少有k个连续的数是该区间中一段的最大和。 n范围在1~10^6。k(-1000~1000); 分析:这道题看似有点像树状数组,但要想求出区间至少有k个连续的和是最大,...
  • //求连续区间的最大和。时间复杂度:O(N^3) const int MIN = numeric_limits<int>::min(); int inefficientMaxSum(const vector<int>& A) { int N = A.size,ret = MIN; for(int i = 0;i ;i++) for(int j = i;j ...
  • 合并区间 ... /** * 输入: [[1,3],[2,6],[8,10],[15,18]] * 输出: [[1,6],[8,10],[15,18]... * 解释: 区间 [1,3] [2,6] 重叠, 将它们合并为 [1,6]. * 必须做事情 * */ public int[][] merge(int[][] interva.
  • 方法概述: 算法1:暴力枚举所有连续子列和,算其中...算法3:分治法,当前处理区间的连续和等于左边最大连续和与右边连续和与跨区间中点连续和的最大值。递归基为区间长度为一的情况,最大连续和就是本身。复杂度\...
  • 显然[l,r]区间的最大子段就是左区间的最大子段,右区间最大子段,以及左右两区间结合在一起中间的最大子段. #include<iostream> #include<cstdio> #include<cstring>...
  • 1、“1 x y”,查询区间 [x,y] 中的最大连续子段。 2、“2 x y”,把 A[x] 改成 y。对于每个查询指令,输出一个整数表示答案。 Input 第一行两个整数N,M。 第二行N个整数A[i]。 接下来M行每行3个整数k,x,y,k=1...
  • 为零的最大连续子数组 思路: 我首先想到是前缀数组,遍历一遍数组,计算出sum[i](表示从0-i子数组之)。 有了前缀数组,只要sum[i]=sum[j](i<j),那么区间[i+1,j]就是为零子数组,只要在...
  • 算法训练 操作格子 时间限制:1.0s 内存限制:256.0MB   问题描述 ...有n个格子,从左到右放成一排,编号为1-n。...3.求连续一段格子的最大值。 对于每个2、3操作输出你所求出结果。 输入格式 第一
  • fun2()使用了Sn进行优化,每次计算区间i~j时候就不需要逐个累加了 fun3()是典型分治法,假设三种情况:起末位置均在mid往左,起末位置均在mid往右,起点在mid往左,终在mid往右。 fun4()是动态规划,使用了状态...
  • 算法描述:维护一个s[p]表示累加 并且更新最大值ans 如果s[p]则从p+1重新累加 证明:设某个区间的起点终点分别为s t 分两种情况 1.t<p:设s2表示1到s累加 s1表示s到t累加 s3表示1到t累积 ...
  • 连续邮资问题要求对于给定nm值,给出邮票面值最佳设计,即在1张信封上可贴出从邮资1开始,增量为1的最大连续邮资区间。例如,当n=5m=4时,面值为(1,3,11,15,32)5种邮票可以贴出邮资的最大连续邮资区间...
  • 这题设计最基本线段树应用,同时考察区间和与区间最值,我采用一个造树函数,一个更新函数和两个查询查询函数,两个查询函数分别返回区间和与区间最大值。       问题描述 有n个格子,从左到右放成一排,编号...
  • 问题描述:给定长度为n整数序列,a...求子区间及其最大值,是非常适合采用分治法德算法设计思想来设计,其分治思想是把一个难以直接解决大问题,分成一些规模较小相同性质问题,以便各个击破,分而治之。如
  • 时间复杂度-----最大区间和

    千次阅读 2017-01-28 15:17:00
    题目大意:在一维数组的连续区间找出其总和最大的连续区间。题目不难,但是很有启迪一道题目。... //方法MaxSum1,MaxSum2都是对数组所有区间进行遍历求和,得出最大值 //求A[]中连续区间的最大和。O(N3) int M
  • 连续子序列的最大和主要由这三部分子区间里元素的最大和得到: 第 1 部分:子区间 [left, mid]。 第 2 部分:子区间 [mid + 1, right]。 第 3 部分:包含子区间[mid , mid + 1]区间,即 nums[mid] 与nums[mid +...
  • Loj-10176-最大连续和

    2019-10-07 07:18:42
    题目 题目链接 ...主要算法: 单调队列优化DP .../*这个代码使用滚动数组优化暴力,有局限性,只能处理长度为m区间的最大连续和,而并不是小于等于m#include<stdio.h> #incl...

空空如也

空空如也

1 2 3 4 5 ... 9
收藏数 175
精华内容 70
关键字:

最大连续区间和的算法