- -

还好吧，分区间求和。

我们从头开始往后加，如果什么时候和小于0了，那么就说明从这儿必然需要分开成两个区间（因为如果从这儿重新开始加的话，是从0开始加的，如果不重新开始加，是从一个负数开始加，显然从0开始加会比较实惠。）

sec_begin = start -> end
   temp = 0;
   sec_pos = sec_begin -> end
      temp += value[sec_pos];
      if (temp < 0) {
         sec_end = sec_pos;
         break;
      }
section[sec_index].begin = sec_begin;
section[sec_index].end = sec_end;
++sec_index;

这样子求出来各个区间，然后每个区间里面从起始处开始加，求出{zd0}的（这个一路扫过去就行了）结果。

然后在所有区间的结果中再找出{zd0}的就行了。

一开始没想到这儿，结果代码有点乱（把同号的数据都合并了），所以处理纯负数数据就处理得很麻烦了。

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;

typedef pair<int, pair<int, int> > data_type; // integer is number value, and the pair is the range it covered. (for single item, pair.first == pair.second)
typedef vector<data_type>::iterator data_vec_iter_type;

data_vec_iter_type
scan(data_vec_iter_type iter_begin, data_vec_iter_type iter_end, data_type& result)
{
   data_type current(*iter_begin);
   data_vec_iter_type iter;
   current.first = 0;
   result = current;

   for (iter = iter_begin; iter != iter_end; ++iter) {
      int temp(current.first + iter->first);
      if (temp < 0) {
         break;
      } else {
         current.first = temp;
         current.second.second = iter->second.second;
         if (current.first > result.first) {
            result = current;
         }
      }
   }

   return iter;
}

void
process_data(vector<data_type>& data, data_type& result)
{
   data_type current;
   data_vec_iter_type tmp;

   result = data.front();

   for (data_vec_iter_type iter = data.begin(); iter != data.end(); ++iter) {
      if (iter->first < 0) {
         continue;
      }
      tmp = scan(iter, data.end(), current) - 1;
      if (tmp > iter) {
         iter = tmp;
      }
      if (current.first > result.first) {
         result = current;
      }
   }

   return;
}

int
main()
{
   int case_count;
   int number_count;
   vector<data_type> data;
   data_type current_data;
   int current_number;
   int case_number(0);
   bool need_endl(false);
   data_type max_negative;

   cin >> case_count;
   while (case_count--) {
      data.clear();
      max_negative.first = -2000;

      data.push_back(make_pair(0, make_pair(0, 0)));
      cin >> number_count;
      while (number_count--) {
         current_data = data.back();

         cin >> current_number;
         if ( (current_number > 0 && current_data.first > 0) || (current_number < 0 && current_data.first < 0) ) {
            current_data.first += current_number;
            ++current_data.second.second;
            data.back() = current_data;
         } else {
            current_data.second.first = ++current_data.second.second;
            current_data.first = current_number;
            data.push_back(current_data);
         }
         if (current_number > max_negative.first) {
            max_negative.first = current_number;
            max_negative.second.first = max_negative.second.second = data.back().second.second;
         }
      }

      data.erase(data.begin());
      if (data.front().first < 0) {
         data.erase(data.begin());
      }

      if (need_endl) {
         cout << endl;
      } else {
         need_endl = true;
      }
      if (data.size()) {
         process_data(data, current_data);
      } else {
         current_data = max_negative;
      }
      cout << "Case " << ++case_number << ":" << endl;
      cout << current_data.first << " " << current_data.second.first << " " << current_data.second.second << endl;
   }

   return 0;
}