Coding-Ninjas/maxlengthchain.cpp at master · kumarvivek8/Coding-Ninjas · 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
#include <bits/stdc++.h>
using namespace std;
struct val
{
    int first;
    int second;
};

map<pair<int, int>, int> m;
int findMaxChainLen(struct val p[], int n,
                        int prev, int pos)
{
    if (m.find({ pos, prev }) != m.end())
    {
        return m[{ pos, prev }];
    }
    if (pos >= n)
        return 0;
    if (p[pos].first <= prev)
    {
        return findMaxChainLen(p, n, prev,
                                 pos + 1);
    }

    else
    {
        int ans = max(findMaxChainLen(p, n,
                             p[pos].second, 0) + 1,
                      findMaxChainLen(p, n,
                                   prev, pos + 1));
        m[{ pos, prev }] = ans;
        return ans;
    }
}
int maxChainLen(struct val p[], int n)
{
    m.clear();
    int ans = findMaxChainLen(p, n, 0, 0);
    return ans;
}
int main()
{

    int n = 5;
    val p[n];
    p[0].first = 5;
    p[0].second = 24;
    p[1].first = 39;
    p[1].second = 60;
    p[2].first = 15;
    p[2].second = 28;
    p[3].first = 27;
    p[3].second = 40;
    p[4].first = 50;
    p[4].second = 90;
    cout << maxChainLen(p, n) << endl;
    return 0;
}