algorithm_trans/test3.cpp at master · NXIST-backup/algorithm_trans · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int, int> pii;

// class Solution
// {
//   public:
//     int lenLongestFibSubseq(vector<int> &arr)
//     {
//         int n = arr.size();
//         vector<int> a;
//         a.push_back(0);
//         for (int i = 0; i < n; i++)
//             a.push_back(arr[i]);

//         map<int, int> dp[1005];

//         for (int i = 1; i <= n; i++) {
//             for (int j = 1; j < i; j++) {
//                 int dif = a[i] - a[j];
//                 dp[i][dif] = 1;
//                 int last = dp[j][dif];
//                 if (j == 1)
//                     last = 1;
//                 dp[i][dif] = max(dp[i][dif], last + 1);
//             }
//         }
//         int ans = 2;
//         for (auto v : dp[n]) {
//             ans = max(ans, v.second);
//         }
//         return ans;
//     }
// };
int dp[1005][1005];
class Solution
{
  public:
    int lenLongestFibSubseq(vector<int> &arr)
    {
        int n = arr.size();
        for (int i = 2; i <= 1000; i++)
            dp[1][i] = 1;
        int ans = 2;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int k = lower_bound(arr.begin(), arr.end(), arr[i] - arr[j]) - arr.begin();
                dp[i][j] = 2;
                dp[i][j] = max(dp[i][j], dp[j][k] + 1);
                ans = max(ans, dp[i][j]);
            }
        }
        return ans > 2 ? ans : 0;
    }
};
int main()
{
    vector<int> arr = {1, 3, 7, 11, 12, 14, 18};
    Solution s;
    cout << s.lenLongestFibSubseq(arr) << endl;
}