写在前边
 
本篇主要记录了最大连续区间和的暴力算法和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;
    }
}
 
 
 
 
 
 
 
 
 
 
 
 

题目：
 连续区间为公差为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]

点击打开链接


最大连续区间和是一个经典的问题。给定一个长度为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;
}

今天做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);
 
}