1 // N <=10^6 2 #include<cstdio> 3 #include<iostream> 4 using namespace std; 5 int n,a[105200]; 6 int maxSubstr(){ 7     int sum=0,minsum=0,answer=0; 8     for(int i=1;i<=n;++i){ 9         sum+=a[i];10         minsum=min(sum,minsum);11         answer=max(answer,sum-minsum);12     }13     printf("%d\n",answer);14 }15 int main()16 {17     scanf("%d",&n);18     for(int i=1;i<=n;i++)19       scanf("%d",&a[i]);20     maxSubstr();21     return 0;22 }

 1 /*二、给你两列数 A; B, 定义一个子串 [l; r] 的权值为 2    ∑r i=l Ai 3 k= ___________ 4    ∑r i=l Bi 5 问权值最大的子串.*/ 6 const double inf = 1e32; 7 int n, a[maxn], b[maxn]; 8 double c[maxn]; 9 double maxSubstr() {10     double sum = 0, minsum = inf, answer = -inf;11     for (int i = 1; i <= n; ++ i) {12         sum += c[i];13         answer = max(answer, sum - minsum);14         minsum = min(sum, minsum);15     }16     return answer;17 }18 double erfen() {19     double l(-inf), r(inf);20     while (l + 1e-10 < r) { 21         double mid = (l + r)/ 2;22         for (int i = 1; i <= n; ++ i) {23             c[i] = a[i] - mid * b[i];24         }25         if (maxSubstr() >= 0) {26             l = mid;27         } else {28             r = mid - 1e-10;29         }30     } //把分母乘过去二分答案31 }