DÃY SỐ C++

Bài toán 1. DÃY SỐ 1 (NBSEQ1)

Tóm tắt đề bài

Cho dãy A có n (1≤n≤10⁵) phần tử. Tính độ dài đoạn con dài nhất chứa các phần tử bằng nhau của dãy A.
INPUT

8

1 2 2 2 3 4 3 4

OUTPUT

3

 

Hướng dẫn giải

Tìm dãy con dài nhất thỏa mãn điều kiện đề bài theo hướng tiếp cận sau: Xét mọi vị trí i, coi i là vị trí cuối cùng của một dãy con nào đó. Ta cần tìm ra độ dài dài nhất của dãy con kết thúc tại i và so sánh với kết quả.
Với hướng tiếp cận này, ta có thể xét được mọi dãy con mà không bị bỏ sót dãy nào cả.

·         Gọi c là độ dài của dãy con liên tiếp dài nhất mà các phần tử đều bằng nhau, phần tử cuối cùng của dãy là phần tử i

·         Gọi res là độ dài dãy con liên tiếp dài nhất mà các phần tử đều bằng nhau, đây chính là kết quả.

·         Ban đầu, khởi tạo c=1,res=c. Mang ý nghĩa là độ dài dãy con kết thúc tại phần tử 1 là 1.

·         Duyệt qua các phần tử ở vị trí i=2 đến i=n

·         Khi xét đến vị trí i thì c chính là độ dài dài nhất của dãy kết thúc tại i−1

·         Ta sẽ tính lại độ dài dãy con kết thúc tại i theo cách: Kiểm tra xem phần tử i có thể ghép tiếp vào dãy trước hay không? (a[i]==a[i−1])?

·         Nếu có thể ghép tiếp thì c+=1. Nếu không thể ghép tiếp thì ta sẽ khởi tạo lại c=1 vì dãy kết thúc tại phần tử i chỉ có duy nhất một phần tử là chính nó nên độ dài là 1

·         Sau khi tính được độ dài dài nhất kết thúc tại phần tử i thì ta sẽ so sánh c với kết quả.

·         Đưa ra kết quả là res

·         1 2 2 2 3 4 3 4

Bài toán 2. DÃY SỐ 2 (NBSEQ2)

Tóm tắt đề bài

Cho dãy A có n (1≤n≤10⁵) phần tử. Tìm độ dài đoạn con dài nhất chỉ chứa các phần tử dương của dãy A.

INPUT

8

1 2 2 -2 3 -4 3 4

OUTPUT

3

Hướng dẫn giải

Tương tự bài trước, nhưng vì khi xét phần tử i, nó có thể thêm được vào dãy cũ hay không phụ thuộc vào nó có dương hay không, không liên quan đến phần tử i−1 nên ta có thể khởi tạo từ đầu và xét i bắt đầu từ 1.

Bài toán 3. DÃY SỐ 3 (NBSEQ3)

Tóm tắt đề bài

Cho dãy A có n (1≤n≤10⁵) phần tử và một số nguyên dương k. Tìm độ dài đoạn con dài nhất chứa các phần tử đều chia hết cho k trong dãy A

INPUT

8 2

1 2 2 -2 6 -4 3 3

OUTPUT

5

Hướng dẫn giải

Tương tự như bài DÃY SỐ #2, thay vì xét các phần tử dương thì ta xét các phần tử chia hết cho k.

Bài toán 4. DÃY SỐ 4 (NBSEQ4)

Tóm tắt đề bài

Cho dãy A có (1≤n≤105) phần tử. Tìm độ dài đoạn con dài nhất chứa các phần tử tăng hoặc giảm dần trong dãy A.

INPUT

8

1 2 2 -2 -2 2 3 5

OUTPUT

4

Hướng dẫn giải

Ta sẽ làm hai lần cho bài này, lần thứ nhất tìm độ dài dãy con tăng dài nhất, lần thứ hai tìm độ dài dãy con giảm dài nhất. Sau đó so sánh và tìm kết quả
Dưới đây là code mẫu cho phần tìm dãy con tăng, phần dãy con giảm chỉ cần làm tương tự.

Bài toán 5. DÃY SỐ 5 (NBSEQ5)

Tóm tắt đề bài

Cho dãy A có (1≤n≤10⁵) phần tử. Tìm độ dài đoạn con dài nhất chứa
các phần tử âm dương đan xen nhau trong dãy A.

INPUT

8

1 2 2 -2 3 -4 3 3

OUTPUT

5

Hướng dẫn giải

Bài này có một lưu ý là: Số 0 không được coi là số âm, cũng không được coi là số dương. Nên khi gặp số 0 thì nó cũng không được tính là một phần tử trong dãy