# 14318: 【原4318】最大平均子区间

### 题目描述

author: smallling 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4318

## Sample Input

9
3 5 3 7 7 6 6 5 6


## Sample Output

7


## ligongzzz's solution

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n;
cin >> n;

int max_n = 0;
for (int i = 0; i < n; ++i) {
int temp;
cin >> temp;
max_n = max(temp, max_n);
}
cout << max_n;
return 0;
}


## zqy2018's solution

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
using namespace std;
typedef long long ll;
int f = 1, x = 0;
char c = getchar();
while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
return f * x;
}
int n, a[1000005], maxi;
void init(){
maxi = 0;
REP(i, 1, n)
a[i] = read(), maxi = max(maxi, a[i]);
}
ll get(int x){
ll mini = 0;
ll ans = -10000000000000000ll, sm = 0;
REP(i, 1, n){
sm += a[i] - x;
ans = max(ans, sm - mini);
mini = min(mini, sm);
}
return ans;
}
void solve(){
int l = 0, r = maxi;
while (r > l){
int mid = (r + l + 1) >> 1;
if (get(mid) >= 0ll)
l = mid;
else r = mid - 1;
}
printf("%d\n", l);
}
int main(){
init();
solve();
return 0;
}