精华内容
下载资源
问答
  • 最大连续区间和的算法
    2017-04-19 17:31:59
    更多相关内容
  • 最大连续区间和算法详解+代码

    千次阅读 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;
        }
    }
    

     

     

     

     

     

     

    展开全文
  • 最大连续区间和算法总结

    千次阅读 2016-04-21 19:00:44
    最大连续区间和是一个经典的问题。给定一个长度为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]);
    }

    当然还有一种方法就是分治法(参考白书上的做法这里给出代码)分三步:
    划分:把问题尽量分成相等的两部分
    递归:递归解决子问题
    合并:合并子问题的解到原问题
    最大连续区间和的 “合并”就是求出起点在左边,终点在右边的最大连续和序列,并和子问题进行比较;
           1---5
    1--3         3--5
    1--2    2--3   3--4   4--5
    代码如下:
    int a[maxn];
    int maxsum(int x,int y){
    int m,v,l,r,Max;
    if(y-x==1)return a[x];
    m=(x+y)>>1;
    Max=max(maxsum(x,m),maxsum(m,y));
    v=0,l=a[m-1];//起点位于左端
    for(int i=m-1;i>=x;i--){
    v+=a[i];
    if(v>l)l=v;
    }
    v=0,r=a[m];//终点位于右端//左闭右开
    for(int i=m;i<y;i++){
    v+=a[i];
    if(v>r)r=v;
    }
    return max(Max,l+r);//递归到终点返回值
    }
    int main()
    {
        #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        #endif
        //freopen("out.txt","w",stdout);
        int n;
        while(cin>>n){
    for(int i=1;i<=n;i++){
    cin>>a[i];
    }
    cout<<maxsum(1,n+1)<<endl;
        }
        return 0;
    }
    时间复杂度 (nlogn)

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


    展开全文
  • 试题 算法提高 最大连续子段

    千次阅读 2022-03-17 15:03:55
    问题描述  给出一个长为n的数列,a1,a2,……... 一个整数,表示最大连续子序列的 样例输入 3 -1 -2 -3 样例输出 -1 数据规模约定  1<=n<=10^5,-10^5<=ai<=10^5 不用动态规划,甚至连long

    问题描述

      给出一个长为n的数列,a1,a2,……,an,求和最大的连续子序列,即找到一对(i,j),i<=j,使ai+ai+1+……+aj的和最大,输出这个和

    输入格式

      第一行为正整数n

      第二行n个用空格分开的整数

      表示a1,a2,……,an

    输出格式

      一个整数,表示最大连续子序列的和

    样例输入

    3

    -1 -2 -3

    样例输出

    -1

    数据规模和约定

      1<=n<=10^5,-10^5<=ai<=10^5

    不用动态规划,甚至连long long 都不用

    #include <stdio.h>
    #include <iostream>
    using namespace std;
    int main(void){
    	int n,max=-100001;
    	cin>>n;
    	for(int x,i=0,t=0;i<n;i++){
    		scanf("%d",&x);
    		t+=x;
    		if(t>max)max=t;
    		if(t<0)t=0;
    	}
    	cout<<max;
    	return 0;
    }

    展开全文
  • 算法专题】区间最大和

    千次阅读 2021-12-08 21:19:02
    此类问题一般是:给出一个序列,让从中选出一些连续的不相交子序列,使得选出的子序列和最大。 子区间长度可能不定,也可能固定。选出的区间数可能是一个,也可能是多个。 如下给出了三个例题: Leetcode 0053...
  • 给定一段长度为N的整数序列A,请从中选出一段连续的子序列(可以为0)使得这段的总和最大
  • 输出和最大连续子串的区间,即第一个数字的位置最后一个数字的位置,并输出这个最大和。 示例: 输入 6 -1 5 4 -7 输出 1 4 14 解释: 区间在1-4 的最大为6+(-1)+5+4 = 14 代码: private static void...
  • 给定n个数A1,A2,A3……An,求两个数l,r满足l并最大化Al+A(l+1)+……Ar,输出这个最大
  • = 1)个整数的序列,求出其中最大连续子序列的。例如序列(34,-20,30,-50,60,-20,30,41,-30,-10)最大子序列为111,序列(-2,11,-4,13,-5,-2)最大子序列为20。规定一个序列的最大连续子序列至少为0。 二、...
  • 贪心算法-求区间至少连续k的最大和

    千次阅读 2013-04-14 16:59:53
    题意:对于一个整数n,表示该区间整数的个数,求至少有k个连续的数是该区间中一段的最大和。 n的范围在1~10^6。k(-1000~1000); 分析:这道题看似有点像树状数组,但要想求出区间至少有k个连续的数的和是最大,...
  • 最大连续区间和的几种方法

    千次阅读 2015-07-11 21:00:54
    今天做bestcoder想到的,几种做最大连续区间和的方法。 定义最大连续区间和:给定一个长度为n的序列a[1],a[2]...a[n],求一个连续的子序列a[i],a[i+1]...a[j-1],a[j]使得a[i]+a[i+1]...+a[j-1]+a[j]最大。 ...
  • 经典算法之分治法 求最大区间和

    千次阅读 2018-04-08 21:23:37
    最大连续段: 5,2,-1,2 其最大为8 解题思路: 制造递归条件,将数组分为两部分. 将区间和分为三部分计算: 第一部分:从begin开始计算[begin, index) 第二部分:从end开始计算[index, end) 第三...
  • 最大连续子序列4种算法解析

    千次阅读 2015-04-16 23:29:34
    给出一个长度为N的序列:a1,a2,……,an,求最大连续和。找到1= 2. 算法1 1) 思路解析:枚举所有可能的子序列的,通过三重循环每次求出一个数组下标范围为[index1, index2]的子序列的,每次求出后进行判断...
  • 一、 算法设计与分析: (1) 数据结构设计: //区间 struct Interval{ int low; int high; }; //节点 struct Node{ Node(int low,int high){ this->key=low; this->Int.low=low; this
  • JAVA算法:求最大子数组乘积问题(JAVA版本) 给定一个整数数组nums,找出一个序列中乘积最大的连续子序列(该序列至少包含一个数)。 问题分析 算法设计 ... * 最大连续子数组乘积 * ...
  • 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个。求所有子数组的最大值。例如数组:arr[]={1, 2, 3, -2, 4, -3 } 最大子数组为 {1, 2, 3, -2, 4} 为8。解法1(时间复杂度O(N * N)空间...
  • 最大子数组的问题可以用到股票市场,比如想得知在一段时间内怎么让股票买进卖出后的利益最大。就可以转化为最大子数组问题。 2,解决方法: (1)暴力枚举法,O(n3) #include "stdafx.h" #include #include #...
  • 引入最大连续区间的概念,以确定带入作业的最大个数,得到了多处理器实时系统中全局EDZL算法的可调度性判定算法。通过构造大量实时任务集,对不同的判定方法进行了实验,检查通过可调度性判定的任务集数量。实验...
  • 试题 算法训练 区间最大和 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述  给定一段长度为N的整数序列A,请从中选出一段连续的子序列(可以为0)使得这段的总和最大。 输入格式  第一行一个整数N表示序列的...
  • 连续子数组的最大和

    万次阅读 多人点赞 2018-09-05 23:06:04
    题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大,当向量全为正数的时候,...给一个数组,返回它的最大连续子序...
  • 求一个数组中连续数字之和最大值。其中连续数字可以从末尾到起始值,举例: 数组:1,-2,1,3,-1,3 最大值:7,数组是1,-2,1,3,-1,3 要求: 数组最大长度是100000 值符合[-2000,2000] 计算时间小于100ms ...
  • 最大子段和三种算法实现

    千次阅读 2021-02-20 12:14:09
    的子段最大值。当所有整数均为负整数时定义其最大子段为 0。依次定义,所求的最优值为 max{ 例如:当(a1,a2,a3,a4,a5,a6)=(-2,11,-4,13,-5,-2)时,最大子段为 =20。 三种算法求解 1、暴力算法 算法分析: ...
  • 针对传统KNN算法忽略样本分布对分类的影响,易受到孤立样本、...同时可处理连续标识型样本分类,并可适应各类样本分布情况,扩大了算法的应用范围.实验结果表明,该算法较传统的近邻算法与邻域分类算法在分类精度与分类
  • 昨天软考(2021年5月29日)试卷上出现了的算法题,问:连续子数组最大和的分治解法的时间复杂度,考完正好总结一下这道算法题。 求连续子数组的最大和 题目描述: 输入一个整型数组,数组里有正数也有负数。 数组...
  • 区间并集求解算法java实现

    热门讨论 2008-10-14 13:07:12
    求解一系列区间并集,目前只支持有限闭区间
  • 给定一个序列,求出其元素和最大的一个子序列。如果序列所有元素为负数,那么规定最大和为0,最大子序列为空。注意子序列里的元素在原序列中是相邻的(不然的话只要把原序列所有正数找出来就行了)。 例 序列:[12, ...
  • 理解最大间隙问题算法

    千次阅读 2020-03-20 19:47:31
    给定 n 个实数,求这n个实数在数轴上相邻2个数之间的最大差值,设计解最大间隙问题的线性时间算法(时间复杂度为O(n))。 输入 1,2,4,3,5,6,7,8,10,19 输出 最大间隙 样例输入 1,2,4,3,5,6,7,8,10...
  • ROS区间分割算法实现逻辑分析

    千次阅读 2021-02-25 20:40:58
    在上一篇中,简单介绍了ROS执行全覆盖路径规划的整体逻辑,其中有一个关键的步骤,是对输入的地图进行区间分割,区间分割的结果直接影响到后续的区间顺序计算以及直线覆盖路径的生成,故本篇对这部分的代码进行分析...
  • 算法训练 操作格子 时间限制:1.0s 内存限制:256.0MB   问题描述 ...有n个格子,从左到右放...2.求连续一段格子权值, 3.求连续一段格子的最大值。 对于每个2、3操作输出你所求出的结果。 输入格式 第一

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 53,200
精华内容 21,280
热门标签
关键字:

最大连续区间和的算法

友情链接: school_java.rar