---
# System prepended metadata

title: THT bảng B (THCS) - 2024 - 3.triseq

---

* time limit per test: **1 seconds**
* points per test: **1.0 points**
* quantity test: **20 testcase**
* memory limit per test: **1024 megabytes**
* input  : **TRISEQ.INP**
* output : **TRISEQ.OUT**
## 1. đề bài ##
**Câu 3: Tam giác**
 cho dãy số **a[1], a[2], ..., a[n]** có **n** phần tử nguyên dương, hãy tìm **dãy con dài nhất (có thể các phần tử không liên tiếp)** của dãy số sao cho ba số nguyên dương bất kỳ trong dãy đều có thể là **ba cạnh của tam giác**.
## 2. input ##
* từ tệp văn bản **TRISEQ.INP** có cấu trúc sau:
    * dòng đầu ghi số nguyên dương **n**.
    * dòng thứ hai ghi **n** số nguyên dương **a[1], a[2], ..., a[n]**. 
## 3.output ##
* ghi vào tệp văn bản **TRISEQ.OUT** ghi số nguyên dương độ dài lớn nhất của dãy con tìm được.
* ***chú ý**: dữ liệu luôn được đảm bảo đáp án từ 3 trở lên.*
## 4. ví dụ ##
* **TRISEQ.INP**
``` 
5
1 2 3 4 5
```
* **TRISEQ.OUT**
```
3
```
* **Giải thích**
```
dãy con thỏa mãn: 2, 3, 4
```
## 5. Subtasks ##
```
Subtasks chung: a[i] ∈ |int32|
Subtasks 1 (30%): 3 <= n <= 15.
Subtasks 2 (40%): 15 <= n <= 1000.
Subtasks 3 (30%): 1000 <= n <= 10^6.
```
## 6. dạng bài ##
* đệ qui
* tham
* twopointer
* toán
## 7. lời giải sơ lược ##
* gọi x, y, z là ba cạnh tam giác.
* --> x+y>z và x+z>y và y+z>x
* Subtasks 1: đệ qui quay lui xác định dãy thỏa mãn điều kiện hoặc sử dụng 3 for để kiểm tra điều kiện thỏa mãn.
* Subtasks 2: sort mảng a, dùng 2 for xác định đoạn [l..r] dài nhất thỏa mãn điều kiện.
* Subtasks 3: sort mảng a, sử dụng kĩ thuật 2 con trỏ tìm đoạn dài nhất thỏa mãn điều kiện. O(nLogn)
## 8. code mẫu ##
```cpp=
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(v) v.begin() , v.end()
#define sz(v) (int)v.size()
#define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
using namespace std;

typedef long long ll;
typedef pair<int , int> ii;
typedef pair<long long , int> lli;

const int maxN = int(1e6)+7;

int n , a[maxN];

namespace sub1{
    bool check(){
        return n <= 15;
    }

    void solve(){
        int ans = 0;
        for (int mask = 0 ; mask < (1<<n) ; mask++){
            vector<int> pos;
            for (int i = 0 ; i < n ; i++) if ((mask>>i)&1) pos.push_back(i + 1);
            bool check = true;
            for (int i = 0 ; i < sz(pos) ; i++){
                for (int j = i + 1 ; j < sz(pos) ; j++){
                    for (int k = j + 1 ; k < sz(pos) ; k++){
                        if (a[pos[i]] + a[pos[j]] <= a[pos[k]]) check = false;
                    }
                }
            }
            if (check == true && __builtin_popcount(mask) >= 3) ans = max(ans , __builtin_popcount(mask));
        }
        cout << ans << "\n";
    }
}

namespace sub2{
    bool check(){
        return n <= 1000;
    }

    void solve(){
        int ans = 0;
        for (int i = 1 ; i <= n ; i++){
            for (int j = i + 2 ; j <= n ; j++){
                if (a[i] + a[i + 1] > a[j]) ans = max(ans , j - i + 1);
            }
        }
        cout << ans << "\n";
    }
}

namespace sub3{
    void solve(){
        int ans = 0;
        for (int i = 1 , j = 0 ; i + 2 <= n ; i++){
            while (j + 1 <= n && a[i] + a[i + 1] > a[j + 1]) j++;
            if (j - i + 1 >= 3) ans = max(ans , j - i + 1);
        }
        cout << ans << "\n";
    }
}

void solve(){
    cin >> n;
    for (int i = 1 ; i <= n ; i++) cin >> a[i];
    sort(a + 1 , a + n + 1);
	
   if (sub1::check()) return sub1::solve();
   if (sub2::check()) return sub2::solve();
   return sub3::solve();
}

#define name "TRISEQ"

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen(name".inp" , "r" , stdin);
    freopen(name".out" , "w" , stdout);
    int t = 1; //cin >> t;
    while (t--) solve();
    return 0;
}

```