Dãy số (THTB Vòng Khu vực 2021)

Xem PDF

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bob gửi cho Alice một dãy số nguyên gồm \(N\) phần tử: \(A_1,A_2,...,A_N\) đây là thông tin về một kho báu. Một đoạn con \((L,R)\) của dãy là một dãy gồm các phần tử liên tiếp \(A_L,A_{L+1},...,A_R\) với \(1\leq L<R\leq N\), đoạn con \((L,R)\) được gọi là chứa thông tin quan trọng nhất nếu:

  • Phần tử đầu tiên bằng phần tử cuối cùng (\(A_L=A_R\)).
  • Tổng các phần tử của đoạn là lớn nhất có thể.

Yêu cầu: Hãy giúp Alice tìm đoạn con chứa thông tin quan trọng nhất.

Input

  • Dòng thứ nhất chứa số nguyên dương \(N\).
  • Dòng thứ hai chứa số nguyên \(A_1,A_2,...,A_N\text{ }(|A_i|\leq 10^9,1\leq i\leq N)\).

Output

  • Ghi ra thiết bị ra chuẩn một số nguyên duy nhất là tổng của đoạn con chứa thông tin quan trọng nhất.

Constraints

  • \(N\leq 10^5\)

Scoring

  • Subtask \(1\) (\(40\%\) số điểm): \(N\leq 10^2\)
  • Subtask \(2\) (\(30\%\) số điểm): \(N\leq 10^3\)
  • Subtask \(3\) (\(30\%\) số điểm): \(N\leq 10^5\)

Example

Test 1

Input
7
3 3 3 3 1 11 1
Output
13

Bình luận


  • 0
    mcsmuscle 11:48 p.m. 25 Tháng 1, 2022

    e viết bằng py, 2 test cuối 11 và 12 của e lỗi 'IndexError', xem test cũng như ko, nhờ mọi người xem fix giúp ạ CODE python


    • 1
      VoBaThongL921 8:48 a.m. 6 Tháng 11, 2021

      ghét mấy ông chép code y hệt trong editorial luôn ạ, không thèm thay tên biến gì luôn. Bí quá thì tham khảo chứ Ctrl C + ctrl V thì ...


      • 0
        trieunguyen_a1 5:27 p.m. 31 Tháng 10, 2021

        how to n = 6 mà có 7 a[i] ????


        • 0
          anh03032007 11:46 p.m. 7 Tháng 10, 2021

          đề này 7-8-9 thi đều được hết hả mọi người


          • 0
            BlockyBlock 9:14 p.m. 6 Tháng 10, 2021

            Ey quên đổi int thành long long, pay 80% test 🙂

            1 phản hồi

            • 1
              LeNam2021 7:36 p.m. 5 Tháng 10, 2021

              Scratch với Time limit 1.0s chạy không kịp các test cuối. Xin Admin nâng Time cho Scratch.


              • 2
                dang7rickroll 7:32 a.m. 5 Tháng 10, 2021

                \(Test\) mẫu ghi \(N = 6\), mà ở dưới lại \(7\) phần tử ?

                2 phản hồi

                • 0
                  VoBaThongL921 9:57 p.m. 4 Tháng 10, 2021

                  Sao test mẫu n = 6 mà dòng dưới có 7 số vậy ạ ?

                  2 phản hồi

                  • -5
                    minhtuanitk20 9:33 p.m. 4 Tháng 10, 2021

                    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.