Cần định hướng làm bài tập tìm độ dài đoạn con liên tiếp dài nhất bao gồm đúng 2 giá trị khác nhau

#1

Em xin mọi người hướng giải bài này bằng c++ ạ

Cho dãy số nguyên . Tìm độ dài đoạn con dài nhất gồm các phần tử liên tiếp của dãy chỉ bao gồm hai giá trị khác nhau. Ví dụ dãy 1, 3, 2, 3, 3, 1, 2 thì đoạn con dài nhất cần tìm là 3, 2, 3, 3 độ dài 4 gồm hai giá trị là 2 và 3.

Dữ liệu : Vào từ file văn bản TWOVALS.INP:

  • Dòng đầu tiên ghi số nguyên ;
  • Dòng thứ hai ghi số nguyên .

Kết quả : Ghi ra file văn bản TWOVALS.OUT một số nguyên duy nhất là độ dài đoạn con dài nhất chỉ bao gồm hai giá trị khác nhau theo phương án tìm được.

Ví dụ

TWOVALS.INP TWOVALS.OUT
7
1 3 2 3 3 1 2		 4
#2

Chắc là dòng đầu tiên ghi độ dài mảng, dòng 2 là các thành phần của mảng chứ nhỉ ?

Định hướng thì:
B1: Xây dựng hàm đọc từ file theo kiểu line by line thì sẽ lấy được giá trị đầu vào là mảng số nguyên.
B2: Xây dựng hàm tìm dãy liên tiếp dài nhất, với:

  • Đầu vào: 1 mảng số nguyên
  • Đầu ra: mảng liên tiếp dài nhất

B3: Xây dựng hàm ghi ra file.
B4: In chiều dài mảng tìm được ở bước 3 ra file.
Xong, vấn đề được giải quyết

3 Likes
#3

Ý em là thuật toán bài này dùng với ạ :frowning:

#4

bạn có test case không? Mình xin test phát

2 Likes
#6 
mãlenght = 0;
for(i...){
    lenght = 0;
    counter = 0;
    for(j...){
        if(counter > 1){
            break;
        }
        if(arr[i] == arr[j]){
            lenght++;
        }
        else{
            lenght++;
            counter++;
        }
    }
    //So sánh lenght với maxlenght...
}

Thử hết như anh @rogp10 đã nói.

1 Like
#7

Chạy như này, mảng dài 1k thì còn chấp nhận được, lỡ độ dài mảng hơi lớn như 10^5 là tạch
Cái này dùng quy hoạch động O(n) thôi.

3 Likes
#8

oops ý mình là bạn thử làm cách tự nhiên nhất.

Khi bạn quét bên phải phần tử thứ i thì bạn thu được thông tin gì?
Bạn sử dụng nó ntn để quét bên trái phần tử thứ j?

4 Likes
#9

bạn xem thử cách mình làm bằng golang.

package main

import "fmt"

func max(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

func main() {
    a := []int{}
    n := len(a)
    if n == 0 {
        fmt.Println(0)
        return
    }
    q := []int{1e9, a[0]}
    mx, t, c := 1, 1, 0
    for i := 1; i < n; i++ {
        if (a[i] - q[0])*(a[i] - q[1]) == 0 || q[0] == 1e9 {
            // trung 1 trong 2 gia tri
            t++
            mx = max(mx, t)
            if q[0] == 1e9 && a[i] != q[1] {
                q = []int{q[1], a[i]}
            }
        } else {
            t = i - c + 1
            q = []int{a[i-1], a[i]}
        }
        if a[i] != a[i-1] {
            c = i
        }
    }
    fmt.Println(mx)
}

cứ chạy rồi kiểm tra thôi :stuck_out_tongue: .

3 Likes
#11 
    int l = 1, r = 1;
    const int MAXN = 1000005;
    int n, a[MAXN] , best = 0;
    int val1 = -1, val2 = -1 , pos = 1, posval = a[1];

    a[n+1] = -1;

    while(r <= n)

    {

        //----(tim 2 gt trong 1 mang)

        if(val1 == -1) val1 = a[r];

        if(val1 != a[r]) val2 = a[r];

        //-------------------------

        if(posval != a[r])

        {

            pos = r;

            posval = a[r];

        }

        if(a[r+1] != val1 && a[r+1] != val2 && val1 != -1 && val2 != -1)

        {

            int length = r - l + 1;

            best = max(best,length);

            l = pos;

            if(val1 == posval) val2 = a[r+1];

            if(val2 == posval) val1 = a[r+1];

        }

        //-------------------------

        r++;

    }

    cout << best << endl;

}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?