ACM-HDU-1003

ACM-HDU-1003

思路:以数组形式存储数据,通过动态规划的思想,状态转移方程A[x]=max(A[x],A[x]+A[x-1])，其中A[x]代表从第1个数到第n个数的连续最大和,再用一个MAx来存连续最大和值，MAX更新时,l,r要进行更新(也要记录A[x]的连续和的l,r以便于后面更新)。
代码:

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,m,i,Mx,l,r,ll,j;
cin >> n;
for(i=1;i<=n;i++){
cin >> m;
int k[m+1];
for(j=1;j<=m;j++){
cin >> k[j];
}
ll=1;
//初始化最大值,因为它可能取到k[1],k[1]>=-1000
Mx=-10000;
for(j=1;j<=m;j++){
if(j!=1){
//状态转移方程
if(k[j]<=k[j-1]+k[j]){
k[j]=k[j-1]+k[j];
}
//变换l
else
{
ll=j;
}
}
//r与j相对应
if(Mx<k[j]){
Mx=k[j];
l=ll;
r=j;
}
}
//输出格式
cout << "Case " << i << ':' <<endl;
cout << Mx << ' ' << l << ' ' << r << endl;
if(i!=n)
cout << endl;
}
return 0;
}

有帮助的小伙伴点个赞咯,会持续更新HDU题目

最后

以上就是秀丽狗为你收集整理的ACM-HDU-1003的全部内容，希望文章能够帮你解决ACM-HDU-1003所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。