Summary: Given a real number sequence \(A=(a_{1},a_{2},\cdots ,a_n)\), an average lower bound \(L\), and an average upper bound \(U\), the Average-Constrained Maximum-Sum Segment problem is to locate a segment \(A(i,j)=(a_i,a_{i+1},\cdots ,a_j)\) that maximizes \(\sum _i \leqslant _k \leqslant _j a_k\) subject to \(L \leqslant (\sum _{i\leqslant k \leqslant j}a_k)/(j-i+1) \leqslant U\). In this paper, we give an \(O(n)\)-time algorithm for the case where the average upper bound is ineffective, i.e., \(U=\infty \). On the other hand, we prove that the time complexity of the problem with an effective average upper bound is \(\Omega (n\log n)\) even if the average lower bound is ineffective, i.e., \(L= - \infty \).