-
Notifications
You must be signed in to change notification settings - Fork 1
/
LIS alternative.cpp
97 lines (77 loc) · 1.79 KB
/
LIS alternative.cpp
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;
int main()
{
int ara[] = {1,2,6,7,10,12,15};
int n = sizeof(ara) / sizeof(n);
int lioes[n];
int max= 1;
int lastindex=0;
bool odd = false, even = false;
for (int i = 0; i < n; i++)
lioes[i] = 1;
for (int i = 1; i < n; i++)
{
cout<<"Step "<<i<<": ";
for (int i = 0; i < n; i++)
cout << lioes[i] << " ";
cout << endl;
for (int j = 0; j < i; j++)
{
if (ara[i] > ara[j] && (ara[i] + ara[j]) % 2 != 0 && lioes[i] < lioes[j] + 1)
{
lioes[i] = lioes[j] + 1;
if (lioes[i] > max)
{
max= lioes[i];
lastindex = i;
}
}
}
}
cout<<"Step "<<n<<": ";
for(int i=0; i<n; i++)
cout<<lioes[i]<<" ";
cout<<endl;
cout<<"MaxSize: ";
cout << max << endl;
vector<int>vec;
int value = ara[lastindex];
int i = lastindex;
if (ara[i] % 2 == 1)
{
odd = true;
even = false;
}
else
{
odd = false;
even = true;
}
cout<<endl;
cout<<"Sequence is: ";
while (max > 0)
{
if ((even &&ara[i]%2==0) && (value > ara[i] || i==lastindex))
{
max--;
vec.push_back(ara[i]);
value = ara[i];
even = false;
odd = true;
}
else if ((odd && ara[i]%2==1)&& (value > ara[i] || i==lastindex))
{
max--;
vec.push_back(ara[i]);
value = ara[i];
even = true;
odd = false;
}
i--;
}
for (int i = vec.size() - 1; i >= 0; i--)
cout << vec[i] << " ";
cout << endl;
return 0;
}