首页 > 代码库 > 杭电1024----Max Sum Plus Plus
杭电1024----Max Sum Plus Plus
1 /* 2 这题还没有理解透彻。某个dalao也不写注释。只能自己理解了。。。 3 先求为i个元素(1<=i<=M)为一个区间的最大和,保证元素个数大于等于i个,递推到M个即可 4 借鉴原址:http://blog.csdn.net/java_wliang/article/details/14214303 5 欢迎讨论 6 */ 7 #include<cstdio> 8 #define maxn 1000005 9 #define inf 1<<30 10 #define Max(a,b) (a)>(b)?(a):(b) 11 int d[maxn],m[maxn],a[maxn]; 12 void init(int n) 13 { 14 for(int i=0; i<n; ++i) 15 d[i] = m[i] = 0; 16 } 17 int main() 18 { 19 int n,M,ans; 20 while(~scanf("%d%d",&M,&n) && n+M) 21 { 22 init(n); 23 for(int i=1; i<=n; ++i) 24 scanf("%d",&a[i]); 25 for(int i=1; i<=M; ++i) 26 { 27 ans = -inf; 28 for(int j=i; j<=n; ++j) 29 { 30 d[j] = Max(d[j-1]+a[j],m[j-1]+a[j]); 31 m[j-1] = ans; 32 ans = Max(ans,d[j]); 33 } 34 } 35 printf("%d\n",ans); 36 } 37 return 0; 38 }
杭电1024----Max Sum Plus Plus
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。