# Dãy đan dấu
## Ý tưởng
Xét các dãy con từ dãy ban đầu để tìm ra dãy con đan dấu dài nhất.

Ví dụ, nếu ta có dãy $A$ $=$ $\{1, 2, -3, 4,-7, 1\}$ thì các dãy con có thể tạo thành là:
- $A_1=\{1, 2, -3, 4,-7, 1\}$
- $A_2=\{2, -3, 4,-7, 1\}$
- $A_3=\{-3, 4,-7, 1\}$
- $A_4=\{4,-7, 1\}$
- $A_5=\{-7, 1\}$
- $A_6=\{1\}$

Các dãy con được tạo có bắt đầu tại một trong số các phần tử của dãy ban đầu.

Từ các dãy con được tạo sẽ xác định được dãy con đan dấu của từng dãy con ấy.

Trong ví dụ trên dãy đan dấu của từng dãy con là:

- $A_1=\{1\}$
- $A_2=\{2, -3, 4,-7, 1\}$
- $A_3=\{-3, 4,-7, 1\}$
- $A_4=\{4,-7, 1\}$
- $A_5=\{-7, 1\}$
- $A_6=\{1\}$

Từ đó, ta sẽ so sánh các dãy đan dấu này để tìm ra kết quả của bài toán.

Vậy dãy đan dấu dài nhất của dãy $A$ ban đầu là: $A_2=\{2, -3, 4, -7, 1\}$.

## Cài đặt
Bước đầu tiên cần làm là tạo ra các dãy con bắt đầu từ các phần tử trong mảng. Điều này có thể thưc hiện bẳng một vòng lặp với biến lặp là $i$.

for (int i=0; i<array.size(); i++){
    //code
}

for i in range(0, len(array):
    #code

Tiếp theo là tìm ra xem dãy đan dấu bắt của từng chuỗi con. Ta sẽ sử dụng một vòng lặp nữa với biến lặp $j$ để xét từng phần tử của dãy con.

Đoạn code dưới đây sử dụng biến ```size``` -kích cỡ của dãy đan dấu, ```start```, ```end``` - chỉ số bắt đầu và kết thúc của dãy đan dấu trong mảng ban đầu.

for (int i=0; i<array.size(); i++){
    int size=0, start=0, end=0;
    for (int j=i; j<array.size(); j++){
        if (i==j){
            size++;
            start=i;
            end=j;
        }
        else{
            if (a[j]*a[j-1]<0){
                size=j-i+1;
                end=j;
            }
            else{
                break;
            }
        }
    }
}

for i in range(0, len(array)):
    size=0
    start=0
    end=0
    for j in range(i, len(array)):
        if i==j:
            size++
            start=i
            end=j
        else:
            if array[j]*array[j-1]<0:
                size=j-i+1
                end=j
            else:
                break

Cuối cùng là so sánh các dãy đan dấu và in ra kết quả.
Ta sẽ sử dụng $3$ biến ```sizeans, startans, endans``` lưu kết quả.

int sizeans=0, startans=0, endans=0;
for (int i=0; i<array.size(); i++){
    int size=0, start=0, end=0;
    for (int j=i; j<array.size(); j++){
        if (i==j){
            size++;
            start=i;
            end=j;
        }
        else{
            if (array[j]*array[j-1]<0){
                size=j-i+1;
                end=j;
            }
            else{
                break;
            }
        }
    }
    if (size>sizeans){
        sizeans=size;
        startans=start;
        endans=end;
    }
}
cout<<sizeans<<"\n";
for (int i=startans; i<=endans; i++){
    cout<<array[i]<<" ";
}

sizeans=0
startans=0
endans=0
for i in range(0, len(array)):
    size=0
    start=0
    end=0
    for j in range(i, len(array)):
        if i==j:
            size++
            start=i
            end=j
        else:
            if array[j]*array[j-1]<0:
                size=j-i+1
                end=j
            else:
                break
    if size>sizeans:
        sizeans=size
        startans=start
        endans=end

Độ phức tạp thời gian: $O(n^2)$.
## Cải tiến
Thay vì xét hết tất cả các dãy đan dấu của từng dãy con, ta có thể xét từng dãy đan dấu của chuỗi ban đầu.

Độ phức tạp thời gian: $O(n)$.