Dãy con có giá trị trung bình lớn nhất
Cho một dãy gồm NN số nguyên A[1],A[2],…,A[N]A[1],A[2],…,A[N]. Tìm dãy con liên tiếp A[L],A[L+1],…,A[R]A[L],A[L+1],…,A[R] (với 1≤L≤R≤N1≤L≤R≤N) trong dãy đã cho có giá trị trung bình lớn nhất.
Giá trị trung bình của dãy con được tính bằng công thức:
Trung bıˋnh=A[L]+A[L+1]+…+A[R]R−L+1Trung bıˋnh=R−L+1A[L]+A[L+1]+…+A[R]
Đầu vào:
- Dòng đầu chứa số nguyên NN.
- Dòng tiếp theo chứa NN số nguyên A[1],A[2],…,A[N]A[1],A[2],…,A[N].
Ràng buộc:
- 1≤N≤1041≤N≤104
- −109≤A[i]≤109−109≤A[i]≤109 với i=1,2,…,Ni=1,2,…,N.
