Bài toán tìm dãy con liên tiếp

Đỗ Thị Hồng Ngát 13/07/2024
Bài toán dãy con liên tiếp
13
Th7

Bài toán tìm dãy con liên tiếp

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

Đây là một bài tập luyện tập trong sách Programming For Newbies của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Tóm tắt đề bài

Cho dãy \(A\) có \(n\) \((1 \le n \le 10^5)\) 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 \(cur\) 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 \(cur=1, res = cur\). 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ì \(cur\) 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ì \(cur+=1\). Nếu không thể ghép tiếp thì ta sẽ khởi tạo lại \(cur=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 \(cur\) với kết quả.
  • Đưa ra kết quả là \(res\)

Code mẫu C++

#include <bits/stdc++.h>
    using namespace std;

    int a[100005];
    int main() {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        int cur = 1;
        int res = cur;
    
        for (int i = 2; i <= n; ++i) {
            if (a[i]==a[i-1]) cur++;
            else cur = 1;
            res = max(res, cur);
        }
    
        cout << res;
    
        return 0;
    }

Code mẫu Python

def main():
    # Đọc số phần tử trong dãy
    n = int(input())

    # Khởi tạo mảng a
    a = [0] * (n + 1)
    for i in range(1, n + 1):
        a[i] = int(input())

    cur = 1
    res = cur

    # Duyệt qua mảng để tìm độ dài dãy con liên tiếp lớn nhất
    for i in range(2, n + 1):
        if a[i] == a[i - 1]:
            cur += 1
        else:
            cur = 1
        res = max(res, cur)

    print(res)

if __name__ == "__main__":
    main()

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

Đây là một bài tập luyện tập trong sách Programming For Newbies của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Tóm tắt đề bài

Cho dãy \(A\) có \(n\) \((1 \le n \le 10^5)\) 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\).

Code mẫu C++

 //Độ dài dãy ban đầu là 0 do chưa có phần tử nào
    int cur = 0;
    int res = cur;

    for (int i = 1; i <= n; ++i) {
        
        if (a[i] > 0) cur++;
        else cur = 0; 
        // Vì độ dài dãy con kết thúc tại phần tử i mà các phần tử đều dương là 0. 
        //a[i] <=0 nên không tính là 1 phần tử của dãy
        
        res = max(res, cur);
    }

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

Đây là một bài tập luyện tập trong sách Programming For Newbies của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Tóm tắt đề bài

Cho dãy \(A\) có \(n\) \((1 \le n \le 10^5)\) 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\).

Code mẫu C++

 //Độ dài dãy ban đầu là 0 do chưa có phần tử nào
    int cur = 0;
    int res = cur;

    for (int i = 1; i <= n; ++i) {
        if (a[i] % k == 0) cur++;
        else cur = 0; 
        res = max(res, cur);
    }

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

Đây là một bài tập luyện tập trong sách Programming For Newbies của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Tóm tắt đề bài

Cho dãy \(A\) có \((1 \le n \le 10^5)\) 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ự.

Code mẫu C++

 //Độ dài dãy ban đầu là 1 vì phần tử 1 cũng là 1 phần tử trong dãy
    int cur = 1;
    int res = cur;

    for (int i = 2; i <= n; ++i) {
        if (a[i] > a[i-1]) cur++;
        else cur = 1;  // Dãy kết thúc tại i chỉ chứa một phần tử là a[i]
        res = max(res, cur);
    }

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

Đây là một bài tập luyện tập trong sách Programming For Newbies của Code Dream, đăng ký mua ngay để được luyện tập nhiều dạng bài về thuật toán khác, chấm bài online tại http://oj.codedream.edu.vn

Tóm tắt đề bài

Cho dãy \(A\) có \((1 \le n \le 10^5)\) 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

Code mẫu C++

 //Độ dài dãy ban đầu là 0 hay 1 phụ thuộc vào phần tử a[1] có được coi là một phần tử của dãy hay không
    //Nếu a[1] = 0, phần tử này không được coi là 1 phần tử của dãy, nên cur = 0
    //Nếu a[1] != 0, phần tử này là 1 phần tử của dãy, nên cur = 1
    int cur = (a[1] != 0);
    int res = cur;

    for (int i = 1; i <= n; ++i) {
        //Nếu phần tử i và i-1 trái dấu
        if (a[i] * a[i-1] < 0) cur++;
        else cur = (a[i] != 0); 
        // Tương tự như lúc khởi tạo, nếu dãy chỉ chứa mỗi phần tử a[i] thì ta xét xem số đó có khác 0 hay không
        
        res = max(res, cur);
    }

Để luyện tập thêm các bài tập về Dãy con liên tiếp, Xử lý mảng trong sách Programming For Newbies, Competitive Programming Basic 2024 của Code Dream, đăng ký mua ngay và chấm bài online tại http://oj.codedream.edu.vn

Xem thêm các thông tin về Code Dream tại: https://www.facebook.com/codedreamedu

Bài viết liên quan:

Bài viết cùng chủ đề:

Đỗ Thị Hồng Ngát

Để lại một bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *