Hướng dẫn cho Học sinh ham chơi


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame


Spoiler Alert


Hint 1

  • Ta chỉ cần tìm \(max_a = max(\forall a_i \in a[])\) của mảng

Chứng minh: \(max_a \geq \frac{max_a * k}{k} \geq \frac{max(a_{i + 1} + a_{i + 2} + ... + a_{i + k}) * k}{k} \geq \frac{a_{i + 1} + a_{i + 2} + ... + a_{i + k}}{k}\)

Reference AC code | O(n) time | O(1) auxiliary space | Online Solving

C++
int main()
{
    int mx = 0;
    for (int n = readInt(); n--; mx = max(mx, readInt()));
    cout << mx;
    return 0;
}


Bình luận


  • 0
    trieunguyen_a1    9:49 p.m. 11 Tháng 9, 2021

    không rõ lắm ạ có ai giảng nhẹ giúp em được không ạ ? Cảm ơn


    • 5
      VoBaThongL921    8:52 p.m. 22 Tháng 9, 2021

      Mình nghĩ là trung bình cộng của mọi dãy con đều bé hơn hoặc bằng phần tử lớn nhất trong mảng ấy. Vậy giá trị lớn nhất chính là phần tử lớn nhất đó, với dãy con có 1 phần tử là phần tử đó luôn