给定K个整数组成的序列{ N?1??, N?2??, ..., N?K?? }，“连续子列”被定义为{ N?i??, N?i+1??, ..., N?j?? }，其中 1。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：
输入第1行给出正整数K (≤)；第2行给出K个整数，其间以空格分隔。
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。
6
-2 11 -4 13 -5 -2
20
好久不写代码，真的生疏了许多啊！！！
分治算法倒是比较常见的这一类问题的解法，o(n*logN)
/* Name: Copyright: Author: 流照君 Date: data Description: */ #include <iostream> #include<string> #include <algorithm> #include <vector> #define inf 100005 using namespace std; typedef long long ll; ll res,n,a[inf]; ll function1(ll l,ll r) { if(r-l==1) return a[l]; ll mid=l+(r-l)/2; ll temp=max(function1(l,mid),function1(mid,r)); ll ans=0; ll v1=a[mid-1]; for(ll i=mid-1;i>=l;i--) v1=max(v1,ans+=a[i]); ll ans1=0; ll v2=a[mid]; for(ll i=mid;i<r;i++) v2=max(v2,ans1+=a[i]); return max(v1+v2,temp); } int main() { //freopen("in.txt", "r", stdin); cin>>n; for(ll i=0;i<n;i++) cin>>a[i]; //function(0,n); res=function1(0,n); if(res<0) cout<<0<<endl; else cout<<res<<endl; //freopen("out.txt", "w", stdout); return 0; }
但是在线处理算法（尺取法）更牛逼 o(n)
/*
Name:
Copyright:
Author: 流照君
Date: data
Description:
*/
#include <iostream>
#include<string>
#include <algorithm>
#include <vector>
#define inf 10005
using namespace std;
typedef long long ll;
int main()
{
//#ifdef ONLINE_JUDGE
//#else
//freopen("in.txt", "r", stdin);
//#endif
ll n,a[inf],temp=0,sum=-inf,r=0,l=0,l1=0,k;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
temp=temp+a[i];
if(temp<0)
{
temp=0;
l=i+1;
}
else if(temp>sum)
{
sum=temp;
r=i;
l1=l;
}
}
//if(sum>=0)
cout<<sum<<endl;
//else
//cout<<0<<" "<<a[0]<<" "<<a[n-1]<<endl;
freopen("out.txt", "w", stdout);
return 0;
}
原文：https://www.cnblogs.com/liuzhaojun/p/12336709.html