DAYSO7 - Dãy số (OLP Không chuyên 2014)

(Giới hạn thời gian: 2.0 giây)

Cho dãy số gồm n số nguyên a₁, a₂, …, a_n. Một đoạn con của dãy đã cho là dãy a_i, a_i+1, …, a_j (1 ≤ i ≤ j ≤ n), dãy có độ dài (j − i + 1) và có trọng số bằng tổng (a_i + a_i+1 + …+ a_j).

Yêu cầu: Tìm hai đoạn con không có phần tử chung, mỗi đoạn có độ dài là một số chia hết cho 3 và tổng trọng số của hai đoạn con là lớn nhất.

Dữ liệu nhập:

- Dòng thứ nhất là số nguyên n (6 ≤ n ≤ 2 x 10⁵).

- Dòng thứ hai là n số nguyên a₁, a₂, …, a_n (|a_i| ≤ 10⁹), mỗi số cách nhau một khoảng trắng.

Dữ liệu xuất:

- Là tổng trọng số của hai đoạn con tìm được.

Ví dụ

• input
  11
  -1 3 -1 -9 -1 1 1 1 1 1 -9
  output
  5

Hai đoạn có tổng lớn nhất là (-1, 3, -1) và (-1, 1, 1, 1, 1, 1)

Lần 1:

* Đặc điểm:

- Dãy con liên tiếp có số phần tử chia hết cho 3 => Sử dụng phương pháp chuyển về tổng 3 số liên tiếp như bài trước.

- Tìm 2 dãy con như vậy.

- n = 10^5 : mà giới gian thời gian 2s => Có thể chấp nhận thuật toán O(n2)

- Đề bài yêu cầu tìm tổng 2 dãy con.

* Ý tưởng ban đầu:

- Tìm T1[i] là tổng lớn nhất dãy con từ đầu đến chứa bộ con t3[i] : O(n)

- Tìm T2[i] là tổng lớn nhất dãy con từ cuối đến chứa bộ con t3[i] : O(n)

- Kết quả cần tìm là max(T[i] + T[j]) với i<j : O(n2)

Let's try! Ăn được đến test 26, như vậy tức là thuật toán đúng, nhưng chưa tối ưu.

Code: http://ideone.com/yTUIIj

Lần 2:

Phần duy nhất chiếm O(n2) chính là phần tìm ra bộ (i<j) max.

Như các bài trước ta đã biết cách để xử lý bài toán tìm bộ (i,j) max này rồi, đó là:

Đầu tiên là tìm fimax[i] = max(0->i) sau đó đi duyệt với j trên fimax đã tính trước đó!

Áp dùng bài toán này!

T1[i] của ta đang có là MAX chưa bộ t3[i], giờ ta tìm T1MAX[i] là tổng lớn nhất tính từ 0->i.

T1MAX[i] = max(T1MAX[i-1],T1[i]); : O(n)

Sau đó, duyệt j trêm T1MAX

kq = max(T1MAX[i] + T2[j]) với i<j : O(n)

*Chú ý: Trong lúc làm bài này sai 2 lần ở chỗ khởi tạo giá trị cho các biến ban đầu của mảng t3, và T1 và T1MAX, giá trị đầu tiên của chúng bắt đầu từ phần tử số 3 (i=2), và khi duyệt chúng ta duyệt bắt đầu từ phần tử thứ 4 (i=3)

Code AC: http://ideone.com/vAuoE8

Bài học:
- Cho dù là thời gian có cho đến 2s, nhưng với n = 10^5 cũng không thể chơi với O(n2) được.
- Kỹ thuật tìm bộ MAX của bộ (i,j) là một kỹ thuật khá quan trọng, vì chủ yếu O(n2) sẽ rơi vào trường hợp này.
- Một lần nữa ôn lại bài toán dãy số có số lượng phần tử chia hết cho 3.

#namlunoy