精华内容
下载资源
问答
  • 最大连续区间和算法详解+代码

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

     

     

     

     

     

     

    展开全文
  • Python求列表的最大连续区间

    千次阅读 2020-02-19 21:00:26
    连续区间为公差为1的等差数列。 输入: [1, 2, 99, 3, 4, 5, 6, 5, 4, 4, 2, 6, 3, 1, 8, 5, 3, 6, 1, 2, 3, 2, 3, 4, 5, 6] 输出: [2, 3, 4, 5, 6] def get_continue_seq(str_list): ls = eval(str_list) ...

    题目
    连续区间为公差为1的等差数列。
    输入:

    [1, 2, 99, 3, 4, 5, 6, 5, 4, 4, 2, 6, 3, 1, 8, 5, 3, 6, 1, 2, 3, 2, 3, 4, 5, 6]

    输出:

    [2, 3, 4, 5, 6]

    def get_continue_seq(str_list):
        ls = eval(str_list)
        len_ls = len(ls)
        index_count = {}
        for x in range(len_ls):
            key = index_count.keys()
            if key:
                diff_x1 = ls[x]-ls[x-1]
                if diff_x1==1:
                    index_count[max(key)].append(ls[x])
                else:
                    index_count[x] = [ls[x]]
            else:
                index_count[x] = [ls[x]]
        res = index_count[max(index_count, key=lambda x: len(index_count[x]))]
        return index_count
    
    str_list = input()
    print(get_continue_seq(str_list))
    
    [1, 2, 99, 3, 4, 5, 6, 5, 4, 4, 2, 6, 3, 1, 8, 5, 3, 6, 1, 2, 3, 2, 3, 4, 5, 6]
    [2, 3, 4, 5, 6]
    
    展开全文
  • 最大连续区间和的算法总结

    千次阅读 2018-02-22 11:15:26
    点击打开链接最大连续区间和是一个经典的问题。给定一个长度为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
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=100;
    //区间设置成 [)
    int a[maxn];
    int maxsum(int x,int y)
    {
    	if(y-x==1)return a[x];//如果设置成x==y的话,容易出现 4 5,无线死循环
    	
    	int m=(x+y)>>1;
    	int Max=max(maxsum(x,m),maxsum(m,y));//m前面不要后面要 
    	int l=a[m-1],v=0;//找起点
    	for(int i=m-1; i>=x; i--) {
    		v+=a[i];
    		if(v>l)l=v;
    	}
    	int r=a[m];v=0;//找终点
    	for(int i=m; i<y; i++) {//i<y 
    		v+=a[i];
    		if(v>r)r=v;
    	}
    	return max(Max,l+r);//比较区间最大值
    }
    int main()
    {
    	int n;
    	scanf("%d",&n);
    	for(int i=1; i<=n; i++) {
    		scanf("%d",&a[i]);
    	}
    	printf("%d\n",maxsum(1,n+1));
    	return 0;
    }
    




    展开全文
  • 最大连续区间和的几种方法

    千次阅读 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]最大。 ...

    今天做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]最大。


    1、根据定义来枚举:枚举上下界i,j,维护一个max值

    其中枚举上下界的复杂度为O(n²),求区间和复杂度为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));


    2、对求区间和的操作做预处理,令sum[i] = a[0] + a[1] + a[2] ... + a[i-1] + a[i]  计算区间和的复杂度可降为O(1),枚举上下界的复杂度不变,所以总的时间复杂度为O(n²)。

    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]);

    3、利用动态规划的思维来继续优化,得到一个线性的基本算法,也是基本连续子区间和的标准算法:

    定义maxn[i]为以i为结尾的最大连续和,则很容易找到递推关系:maxn[i] = max{0,max[i-1] + a[i]} 

    所以只要扫描一遍即可,总时间复杂度为O(n)。

    for(int i =1; i <= n; i++)

    {

    last = max(0,maxn[i-1]) + a[i];

    ans = max(ans,last);

    展开全文
  • 最大子数组的问题可以用到股票市场,比如想得知在一段时间内怎么让股票买进卖出后的利益最大。就可以转化为最大子数组问题。 2,解决方法: (1)暴力枚举法,O(n3) #include "stdafx.h" #include #include #...
  • 题目:有一个数组,求他的最大(最长)连续区间(数字是连续的区间)。 我的解法,如下: class Finder(object): ''' 判断两个相邻的数字是否连续,若连续: 1.继续向后判断 2.记录连续长度 最后返回...
  • 求一个数组中,一段连续区间最大和。 dp(i+1)=max(num[i+1], num[i+1]+dp(i)); dpi表示以第i元素结尾的最大区间和。 #include<iostream> using namespace std; int main() { int n; cin>>n; int* a...
  • 传送门
  • 、a_n,请找出在所有连续区间 中,区间和最大同时这个区间 0 的个数小于等于 3 个,输出这个区间和。 输入描述: 第一行一个正整数 n, 表示数组长度,1 &amp;amp;lt;= n &amp;amp;lt;= 1000000。 第二行...
  • 题意 有n个连在一起的地道 接下来有m个操作 D x 炸掉x号地道 炸掉后x所在的区间就不连续了 Q x 查询输出包括x的最大连续区间长度 R修复最后一个被炸的地道 注意输入R时可能并没有需要修复的地道 线段树的区间...
  • 做kuangbin线段树专题的时候遇到...题意:1-n个地道,m个次操作,D代表摧毁第i个地道,Q代表查询包含第i个地道的最大连续地道数目,并输出。R代表修复最近摧毁的那个地道; 解题的关键思路&过程:这个题目一开...
  • 线段树结点 设置一个 ls 记录区间左端点开始的最大连续个数, rs 记录区间右端点开始的最大的连续个数, ms表示该区间最大的连续点的个数。 #include #include #include #include #include #include #i
  • Oracle求连续区间内的最大最小值

    千次阅读 2017-10-31 20:57:22
    现在有一组数据记录了NBA球队每年的夺冠队伍,如下: 要求求出连续夺冠的队伍和连续年月,效果如下: 首先要判断一个队是否连续夺冠,...最后就是很基础的分组求最大最小值过程了,就不再赘述了。最终sql如下: s
  • /* 在区间中,有三种操作, Q x 查询包含x的最长连续区间 D x 将x点毁掉即x点左右不再连续 R 修复上一次毁坏的点 ... 所以直接将该右孩子区间的左连续区间加上其兄弟区间的右连续区间即是最终结果。
  • /************************************** 题目大意: 一条直线上的有n个顶点;...线段树,求最大连续区间,操作类似于pku3667; ls 记录区间左端点开始的最大连续个数, rs 记录区间右端点开始的最大的连续个
  • 题意:给一个数组,求任意区间最大连续和 长度n,查询次数m n,m大小是5*10^5 每个数不超过1e9 之前做的是静态数组求一次最大连续和,方法有很多,dp之类的都能o(n)解决。 还有一个是分治法,nlogn解决:...
  • 题解:某大佬的区间子段和的解释:https://blog.csdn.net/wu_tongtong/article/details/73385029 ...[x,y]内的最大子段和 ms [x,y]的区间和 s [x,y]内的紧靠左端点的最大子段和 ls [x,y]内的紧靠右端点的最大子...
  • For an array b of length m we define the function f as f(b)={b[1]ifm=1f(b[1]⊕b[2],b[2]⊕b[3],…,b[m−1]⊕b[m])otherwise, where ⊕ is bitwise exclusive OR. For example, f(1,2,4,8)=f(1⊕2,2⊕4,4⊕...
  • 最大连续区间和-dp

    2015-05-29 15:02:21
    ///最大连续区间和有两种情况, //1是不跨界 2是跨界 //对于不跨界,我们dp求一次就得到不跨界的最大和 //对于跨界的,我们反过来想,除去跨界的最大连续和后 剩下的必然是最小连续和,而且//必定小于等于0 ,否则的...
  • 题意 :给一个正整数数列,求一个平均数最大且长度不小于L的连续子串,输出平均值*1000 先谈谈我对求区间子串最大值的理解 ; 1.没有长度限制: 按方向遍历,保存0~i的值,假如这个值小于0,则令这个值等于...
  • SQL 查询连续区间

    千次阅读 2019-07-14 05:52:58
    Technorati 标签: SQL Server,T-SQL,查询,连续区间,row_number函数 这篇文章演示如何查询连续区间。 首先创建一个实验表,并插入测试数据。 create table tbl(num int not null primary key) go insert into tbl...
  • MATLAB求指定区间连续函数最大/最小值 首先,最大值和最小值问题都可以看成是最小值问题,因为只要对函数乘个符号就可以把最大值问题转化成最小值问题。 求最小值问题可以通过求极小值和边界函数值实现。 1. 利用...
  • 斐波那契搜索一个变量中未知单峰函数的最大值x = fibosearch(fhandle,a,b,npoints) a,b 定义分辨率为 1/npoints 的搜索间隔
  • 连续邮资问题

    千次阅读 2018-07-18 15:27:11
    连续邮资问题要求对于给定的n和m的值,给出邮票面值的最佳设计,在1张信封上可贴出从邮资1开始,增量为1的最大连续邮资区间。  例如,当n=2、m=3时,如果面值分别为1、4,则在l-6之间的每一个邮资值都能得到(当然...
  • 区间最大平均值

    千次阅读 2020-05-18 18:50:43
    最大区间平均值,可以先想求又没有区间平均值大于一个固定值A 即在这个序列里 a1 a2 a3 .... ai ... aj ..... an ..a_1\ a_2 \ a_3 \ .... \ a_i \ ... \ a_j \ ......
  • 区间异或最大

    千次阅读 2018-08-24 12:24:51
    然后有M个询问,每次询问给定一个整数X,让你找一个Ai使得Ai xor X的值最大。 这道题也是可以用Trie解决的。首先我们知道一个整数可以用二进制表示成一个01串。比如3=(011)2, 5=(101)2, 4=(100)2……。我们假设输入...
  • //求连续区间最大和。时间复杂度: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 ...
  • 【例题】【线段树】连续区间

    千次阅读 2016-07-14 22:16:19
    NKOJ 2753 区间连续值 时间限制 : 10000 MS 空间限制 : 65536 KB 问题描述 有一数列只有0和1构成,数列中数字个数为为n。 现在有m个形式为x y的提问,询问区间[x,y]中,最多有多少个连续的1。 对于每个询问,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 78,283
精华内容 31,313
关键字:

最大连续区间