神的代码

(25分) 给定数列a0,a1…an，求和最接近0的连续子序列，如果有多个，输出所有子序列，每个一行。

 

比如数列为-1,3,1,-2,4,1时，和最接近0的连续子序列有2个，和都是1，分别是1,-2和-1,3,1,-2，还有单独的-1和1共三个。

 

输入输出格式均为每行一个数列，数间用空格分隔。

 

有多个子序列时，先输出开始位置更前的。若开始位置相同，输出结束位置更前的。

 

输入示例

 -1 3 1 -2 4 1

1 2 3

 

输出示例

 -1

-1 3 1 -2

1

1 -2

1

1

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

vector<int> data;
int ans;

char key[1000000];


int main() {
    string x;

    while (gets(key)) {
        x = key;
        ans = INT_MAX;
        stringstream sin(x);
        int t;
        data.clear();
        while (sin >> t) {
            data.push_back(t);
        }
        for (int i = 0; i < data.size(); ++i) {
            int sum = 0;
            for (int j = i; j < data.size(); ++j) {
                sum += data[j];
                ans = min(ans, abs(sum));
            }
        }

        for (int i = 0; i < data.size(); ++i) {
            int sum = 0;
            for (int j = i; j < data.size(); ++j) {
                sum += data[j];
                if (abs(sum) == ans) {
                    for (int k = i; k <= j; ++k) {
                        if (k != i) {
                            printf(" ");
                        }
                        printf("%d", data[k]);
                    }
                    puts("");
                }
            }
        }
    }

}