题目：
这题要求大于0的最小字段和，常规O（n）求最大字段和的方法肯定是没法解的。
我的解法是：用sum[i]存前i项的和，也就是前缀和。
这题就变成了求sum[j]-sum[i]的大于0的最小值( j > i )。
我们可以看到直接循环运算量是50000*50000，会超时。
所以我们应该充分利用前缀和的特性。
我们用一个set容器来装sum。
当算到i项时，保证前i-1项已经装入了set中。
我们用二分查找找到第一个比sum[i]小的值，用sum[i]减去这个值来更新答案。
至于二分插入，set容器中插入数据用的就是二分插入。
代码：
#include <bits\stdc++.h> using namespace std; typedef long long ll; ll sum[50010]; // sum[i]表示 1~(i-1) 项的和 set <ll> s; // 到第i项时，s存的是 sum[1]~sum[i-1] set <ll>::iterator it; //迭代器 int main() {int n;cin >> n;int mn = 2000000000;int key;for(int i = 1;i <= n; i++){cin >> key;sum[i] = sum[i-1]+key;}s.insert(0);for(int i = 1;i <= n; i++){// lower_bound返回大于等于sum[i]的最小值// upper_bound返回大于sum[i]的最小值 it = s.lower_bound(sum[i]);if(it != s.begin()){ it--;//it表示小于sum[i]的最大值 if(sum - *it > 0){mn = min((ll)mn,sum[i]-*it);}} s.insert(sum[i]);}cout << mn << endl;return 0; }
