題目描述：

給定一個整數序列，你會求最大子串和嗎？幾乎所有的數據結構與算法都會描述求最大子串和的算法。今天讓大家來算算最近0子串和，即整數序列中最接近0的連續子串和。例如，整數序列6, -4, 5, 6中，連續子串｛－4，5｝的和為1，比其他任何連續子串的和都更接近0。該整數序列的最近0子串和就是1.

輸入：

每個測試文件包含多個測試案例，每個測試案例兩行，第一行包括一個整數N，代表整數序列的長度，第二行是以空格隔開的N個整數，代表該整數序列。其中我們能保證1 <= N <= 10⁵，每個整數大于等于－2³⁰且小于2³⁰.

輸出：

對于每個整數序列，輸出一行，包含一個整數，即最近0子串和。如果同時存在多個解（如－1, 3, 1存在－1和1兩個解），則輸出最大的一個（輸出1）。

樣例輸入：

4 6 －4 5 6 2 －1 1

樣例輸出：

1 0

這個題一開始思考有沒有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 6 41 //6 2 7 13

?

轉載于:https://www.cnblogs.com/jasonJie/p/5811540.html

總結

以上是生活随笔為你收集整理的九度oj 题目1376：最近零子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。