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

Xem PDF
Tác giả:
Small
Dạng bài
Đ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
    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 ạ ?


    • 7
      longkold00    8:32 a.m. 6 Tháng 10, 2021 ← đã chỉnh sửa
      1. Bài này sử dụng hash_map gán tất cả m[ai]=1e16 để lưu vết tổng nhỏ nhất từ a1->a[i-1] theo công thức m[a[i]]=min(m[a[i]],sum-a[i]);
      2. Tạo 1 biến sum=0 để lưu tổng các số từ a[1]-> vị trí đang xét.
      3. tạo 1 biến res là kq cần tìm, lúc này res đc tính theo công thức res=max(res,sum-m[a[i]]);

      hash_map trong c++ là lớp unordered_map; sum-m[a[i]] để tính tổng các số từ vị trí a[i] có m[a[i]] nhỏ nhất đến vị trí a[i] đang xét


      • 0
        hoanganhthcsnd    10:40 a.m. 17 Tháng 7, 2023

        chỗ bước 1 thì sum đấy là j vậy bạn


        • 0
          VoBaThongL921    8:35 a.m. 6 Tháng 10, 2021 ← chỉnh sửa 2

          Vâng ạ, em đang học online nên tí nữa em đọc nhé anh


          • 1
            longkold00    8:38 a.m. 6 Tháng 10, 2021

            cách thức dùng thì giống nhau nhé, khác ở chỗ truy suất phần tử thì hash tốn ít thời gian hơn :v


            • 0
              NguyenTN09112006    5:02 p.m. 7 Tháng 10, 2021

              bài này sài mảng cộng dồn dc ko a


              • 1
                longkold00    9:45 p.m. 7 Tháng 10, 2021

                mảng cộng dồn là lại bị tle :V


        • 0
          longkold00    8:22 a.m. 6 Tháng 10, 2021

          :v a viết hint cho nhó :V

        8 bình luận nữa