首页 > 代码库 > 九度oj 题目1376:最近零子序列
九度oj 题目1376:最近零子序列
- 题目描述:
- 给定一个整数序列,你会求最大子串和吗?几乎所有的数据结构与算法都会描述求最大子串和的算法。今天让大家来算算最近0子串和,即整数序列中最接近0的连续子串和。例如,整数序列6, -4, 5, 6中,连续子串{-4,5}的和为1,比其他任何连续子串的和都更接近0。该整数序列的最近0子串和就是1.
- 输入:
- 每个测试文件包含多个测试案例,每个测试案例两行,第一行包括一个整数N,代表整数序列的长度,第二行是以空格隔开的N个整数,代表该整数序列。其中我们能保证1 <= N <= 105,每个整数大于等于-230且小于230.
- 输出:
- 对于每个整数序列,输出一行,包含一个整数,即最近0子串和。如果同时存在多个解(如-1, 3, 1存在-1和1两个解),则输出最大的一个(输出1)。
- 样例输入:
46 -4 5 62-1 1
- 样例输出:
10
这个题一开始思考有没有O(n)的办法,结果并没有找到很好的办法
于是只好按O(n2)的办法做,试着提交,居然没超时
代码如下1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 int n; 6 typedef long long ll; 7 int num[100002]; 8 ll sum[100002]; 9 10 int main(int argc, char const *argv[])11 {12 while(scanf("%d",&n) != EOF) {13 sum[0] = 0;14 for(int i = 1; i <= n; i++) {15 scanf("%d",&num[i]);16 sum[i] = sum[i-1] + num[i];17 }18 int min = 999999999;19 for(int i = n; i >= 1 && min != 0; i--) {20 for(int j = i-1; j >= 0 && min != 0; j--) {21 ll tmp = sum[i] - sum[j];22 if(abs(tmp) < abs(min)) {23 min = tmp;24 }25 if(abs(tmp) == abs(min)) {26 if(tmp >= 0) {27 min = tmp;28 }29 }30 if(min == 0) {31 break;32 }33 }34 } 35 printf("%d\n",min);36 }37 return 0;38 }39 40 //6 -4 5 641 //6 2 7 13
九度oj 题目1376:最近零子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。