HDU 1003 最大连续子段和
2024-10-20 05:26:15
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1003
Max Sum
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
#### 问题描述
> Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
#### 输入
> The first line of the input contains an integer T(1 For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
样例输入
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
样例输出
Case 1:
14 1 4Case 2:
7 1 6
题意
求最大连续子段和，多解时求最左边那个。
题解
1、写wa了。。
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<sstream>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=101010;
int arr[maxn],n;
int main() {
int tc,kase=0;
scf("%d",&tc);
while(tc--){
scf("%d",&n);
for(int i=1;i<=n;i++) scf("%d",&arr[i]);
int l=1,r=1,Ma=arr[1];
for(int i=1;i<=n;i++){
int tmp=arr[i];
if(tmp>Ma){ Ma=tmp,l=r=i; }
int ed=i+1;
//这里其实强行把第i个塞进去了，这是错的。
while(ed<=n&&tmp+arr[ed]>=0){
tmp+=arr[ed];
if(tmp>Ma){
Ma=tmp;
l=i,r=ed;
}
ed++;
}
i=ed-1;
}
prf("Case %d:\n",++kase);
prf("%d %d %d\n",Ma,l,r);
if(tc) prf("\n");
}
return 0;
}
2、改的很挫，终于过了。。
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<sstream>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=101010;
int arr[maxn],n;
int main() {
// freopen("data_in.txt","r",stdin);
// freopen("data_out.txt","w",stdout);
int tc,kase=0;
scf("%d",&tc);
while(tc--){
scf("%d",&n);
for(int i=1;i<=n;i++) scf("%d",&arr[i]);
int l=0,r=0,Ma=-INF;
for(int i=1;i<=n;i++){
if(arr[i]<0){
if(arr[i]>Ma){
Ma=arr[i];
l=r=i;
}
continue;
}
int tmp=arr[i];
if(arr[i]>Ma){
Ma=arr[i];
l=r=i;
}
int ed=i+1;
while(ed<=n&&tmp+arr[ed]>=0){
tmp+=arr[ed];
if(tmp>Ma){
Ma=tmp;
l=i,r=ed;
}
ed++;
}
i=ed-1;
}
prf("Case %d:\n",++kase);
prf("%d %d %d\n",Ma,l,r);
if(tc) prf("\n");
}
return 0;
}
//end-----------------------------------------------------------------------
3、来个正常点的思路：
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<sstream>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=101010;
int arr[maxn],n;
int main() {
// freopen("data_in.txt","r",stdin);
// freopen("data_out.txt","w",stdout);
int tc,kase=0;
scf("%d",&tc);
while(tc--){
scf("%d",&n);
for(int i=1;i<=n;i++) scf("%d",&arr[i]);
int sum=0,l=1,r=1,tmp=1,Ma=-INF;
for(int i=1;i<=n;i++){
if(sum<0){
sum=0; tmp=i;
}
sum+=arr[i];
if(sum>Ma){
Ma=sum;
l=tmp,r=i;
}
}
prf("Case %d:\n",++kase);
prf("%d %d %d\n",Ma,l,r);
if(tc) prf("\n");
}
return 0;
}
//end-----------------------------------------------------------------------最新文章
- __new__方法
- 根据BOM和已存在的文件生成文件列表
- GL_GL系列 - 多币种管理分析（案例）
- poj3468(线段树 边覆盖)
- (转载)NET流操作
- stat命令
- Java 三目运算符表达式的一些问题
- mybatis 自动生成代码（mybatis generator）
- ubuntu10.04 安装配置tftp服务
- Linux挖矿病毒 khugepageds详细解决步骤
- webpack热更新和常见错误处理
- 单个 LINQ to Entities 查询中的两个结构上不兼容的初始化过程中出现类型“XXXX”
- Ext.js项目（一）
- SLAM学习笔记 - ORB_SLAM2源码运行及分析
- linux 程序实现后台运行
- HDU6043 17多校1 KazaQ's Socks 水题
- 【机器学习】从分类问题区别机器学习类型 与 初步介绍无监督学习算法 PAC
- android开发(27) 看看我的手机里都有什么传感器
- 根据时间获取最新数据 SQL(每一个人或者每一项)
- Sum Problem