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

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

     

     

     

     

     

     

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

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




    展开全文
  • 贪心算法-求区间至少连续k的最大和

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

    题意:对于一个整数n,表示该区间整数的个数,求至少有k个连续的数是该区间中一段的最大和。

    n的范围在1~10^6。k(-1000~1000);

    分析:这道题看似有点像树状数组,但要想求出区间至少有k个连续的数的和是最大,恐怕是有点难度,顶多是求某一区间的和。

    不过可以沿着这个思路想,sum(n)-sum(i)?。

    如果这样想,我们就要判断n-i>=k;那换种思路:在第i的前面寻找最小值,在i+k的后面寻找最大值。这样sum(n)-sum(i)一定是第i个循环中最大的一个。

    对于每次这样循环,我只要定义一个变量来接收一个最大值(sum(n)-sum(i))把它与下一个做比较就行了。

    思路清晰了,代码应该就好写了。

    #include<cstdio>
    #include<iostream>
    using namespace std;
    int n,k;
    int a[1000005];
    int INF=0x7fffffff;
    void maxsum()
       {  
          int l=INF;                              //值最大,能把值传递给l(小于它的值)。
          int r=INF+1;                            //值最小,能把值传递给r(大于它的值)。
         for(int i=k;i<=n;i++)
          {
    	    l=l<a[i-k]?l:a[i-k];      //在i-k个前面检测最小的值,每次i++;比较的范围至少相差k个。
            r=r>a[i]-l?r:a[i]-l;      //在i个以后检测最大值。
    	 }                           
         cout<<r<<endl; 
    }
    int main()
    {    
        while(scanf("%d%d",&n,&k)!=EOF)
    	{
         for(int i=1;i<=n;i++)
         {
           cin>>a[i];
           a[i]+=a[i-1];
         }
    	 maxsum();
    	}
         return 0;
    }
           
    


    展开全文
  • 最大子数组的问题可以用到股票市场,比如想得知在一段时间内怎么让股票买进卖出后的利益最大。就可以转化为最大子数组问题。 2,解决方法: (1)暴力枚举法,O(n3) #include "stdafx.h" #include #include #...
  • 最大连续区间和的几种方法

    千次阅读 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]最大。 ...
  • //求连续区间最大和。时间复杂度: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 ...
  • 最大连续段: 5,2,-1,2 其最大为8 解题思路: 制造递归条件,将数组分为两部分. 将区间和分为三部分计算: 第一部分:从begin开始计算[begin, index) 第二部分:从end开始计算[index, end) 第三...
  • 系统界面有多个输入框 比如 1:>24 2: 3: 大于等于5 并且小于等于24 真实环境 可能不仅仅是三...现在求一个算法 来判断用户输入的多个区间 不能重叠,同时还要校验用户输入的区间是一个闭环? 有案例代码 最好
  • /************************************** 题目大意: 一条直线上的有n个顶点;...线段树,求最大连续区间,操作类似于pku3667; ls 记录区间左端点开始的最大连续个数, rs 记录区间右端点开始的最大的连续个
  • 例题四:最大连续子序列(线性型:最大连续子序列的模型) 题目: 求给定序列的最大连续子序列。 输入: 第一行:n(N&amp;lt;100000) 第二行:n个整数(-3000,3000)。 输出: 最大连续子序列的...
  • 算法 - 求子数组的最大和(C++)

    万次阅读 多人点赞 2019-02-27 18:11:55
    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍...数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个。 * 求所有子数组的最大值。要求时间复杂度为O(n...
  • 最大连续子序列4种算法解析

    千次阅读 2015-04-16 23:29:34
    给出一个长度为N的序列:a1,a2,……,an,求最大连续和。找到1= 2. 算法1 1) 思路解析:枚举所有可能的子序列的,通过三重循环每次求出一个数组下标范围为[index1, index2]的子序列的,每次求出后进行判断...
  • 假设一个国家发行了n种面值的邮票,面值已知,并规定每封信上最多只能贴m张邮票,设计一个算法,求出在一个信封上能贴出的最大连续区间. 例如发行了4种邮票面值分别为1,4,12,21.每封信上最多能贴5张邮票,求出能贴出的...
  • 首先明确一下贪心算法的核心思想:局部最优导致全局最有 下面是实现的例子:
  • 算法训练 操作格子 时间限制:1.0s 内存限制:256.0MB   问题描述 ...有n个格子,从左到右放...2.求连续一段格子权值, 3.求连续一段格子的最大值。 对于每个2、3操作输出你所求出的结果。 输入格式 第一
  • 数据结构、动态规划、基础排序、暴力算法
  • 使用Kadane算法可以在On内得到最大连续子序列。如果要求得到不超过k,那么该如何解决? 首先要看能不能继续使用Kadane算法。答案是不能。回顾Kadane,Kadane中使用dp[i]存最后一个元素是array[i]的最大,然后...
  • 连续邮资问题要求对于给定的nm的值,给出邮票面值的最佳设计,即在1张信封上可贴出从邮资1开始,增量为1的最大连续邮资区间。例如,当n=5m=4时,面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间...
  • 当 当 当 当 ~~ 没错,又是算法课作业 (╯︵╰)问题...输出:序列的一个连续子段,使该子段和最大 当所有整数都为负数时,定义最大子段为0 语言:c++若要输出连续子段,见链接(眼神不好,交作业才读懂题): ...
  • 因为这些元素的最大连续和区间,可能在这个中点左面,也可能在中点的右面,也可能在中点的左右各有一部分。 所以把这个问题分为三部分讨论。 想求它的最大连续和,要先把它中点左面的最大连续和求出来,还要...
  • 时间复杂度为n的方法:import java.util.Scanner;class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int sum = 0, sum1 = 0, f
  • RMQ算法 快速求区间最大最小值

    千次阅读 2015-08-10 15:13:59
    RMQ基本上就是来求区间嘴子问题的 maxsum【i】【j】表示从数字num【】下表i开始的后1 开始初始化两个数组  for(i=1;i  {  maxsum[i][0]=minsum[i][0]=num[i];  } 然后dp经行跟新  int k=log2(n);...
  • 求一个数组中连续数字之和最大值。其中连续数字可以从末尾到起始值,举例: 数组:1,-2,1,3,-1,3 最大值:7,数组是1,-2,1,3,-1,3 要求: 数组最大长度是100000 值符合[-2000,2000] 计算时间小于100ms ...
  • 输入一个整形数组,求数组中连续的子数组使其和最大。比如,数组x 应该返回 x[2..6]的187. 2. 问题解决 我们很自然地能想到穷举的办法,穷举所有的子数组的之,找出最大值。 穷举法 ...
  • 时间复杂度-----最大区间和

    千次阅读 2017-01-28 15:17:00
    题目大意:在一维数组的连续区间找出其总和最大连续区间。题目不难,但是很有启迪的一道题目。... //方法MaxSum1,MaxSum2都是对数组的所有区间进行遍历求和,得出最大值 //求A[]中连续区间最大和。O(N3) int M
  • RMQ问题, ST算法
  • 算法在最坏情况下时间复杂度为O(nlongn) class Solution(object): def lengthOfLIS(self, nums): """ :type nums: List[int] :rtype: int """ theL = len(nums) if theL theDp = [0 for i in range...
  • 贪心算法-整数区间-JAVA

    千次阅读 2015-02-08 16:20:23
    贪心算法-整数区间 【题目描述】  我们定义一个整数区间[a,b],a,b是一个从a开始至b 结束的连续整数的集合。编一个程序,对给定的 n个区间,找出满足下述条件的所含元素个数最少的集合中元素的个数:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,225
精华内容 17,690
关键字:

最大连续区间和的算法