pat 1007

发布时间:2016-12-9 4:16:39 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"pat 1007",主要涉及到pat 1007方面的内容,对于pat 1007感兴趣的同学可以参考一下。

Maximum Subsequence Sum 思路:这个题就是最大连续子串和,并且要求输出子串在原串中的起始和结束位置 动态规划的经典问题 附代码: #include<stdio.h> #include<stdlib.h> #include<string.h> #define Max_len 10010 int record[Max_len]; //-2 11 -4 13 -5 -2 typedef struct node{ int value; int front; }node; node no[Max_len]; int main(){ int n, i; int pos, max, num = 0; scanf("%d", &n); for(i = 0; i < n; i++){ scanf("%d", &no[i].value); no[i].front = i; record[i] = no[i].value; if(no[i].value < 0){ num ++; } } if(num == n){ printf("%d %d %d\n", 0, no[0].value, no[n - 1].value); return 0; } for(i = 1; i < n; i++){ if(no[i - 1].value > 0){ no[i].value += no[i - 1].value; no[i].front = no[i - 1].front; } } max = no[0].value; pos = no[0].front; for(i = 1; i < n; i++){ if(no[i].value > max){ pos = i; max = no[i].value; } } printf("%d %d %d\n", max, record[no[pos].front], record[pos]); return 0; }

上一篇:quartz学习
下一篇:informix数据库中批量导入部分表的数据到另外一个相同的数据库中

相关文章

关键词: pat 1007

相关评论