Longest Increasing Subsequence (LIS)

Resource:

Longest Increasing Subsequence (GFG) 

LIS and variation  

ডাইনামিক প্রোগ্রামিং এ হাতেখড়ি-৪ 

Problem:

990 - Diving for Gold 

1501. Sense of Beauty 

1167. Bicolored Horses 

231 - Testing the CATCHER 

10926 - How Many Dependencies? 

10000 - Longest Paths 

XMEN   SOLUTTION

10635 - Prince and Princess 

1277 - Looking for a Subsequence    SOLUTION

  Code:

 

	//https://www.geeksforgeeks.org/longest-common-increasing-subsequence-lcs-lis/
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	// O(n*m)
	int LCIS(int a1[], int n, int a2[], int m)
	{
	int table[m], parent[m];
	for (int i = 0; i < m; i++) table[i] = 0;
	for (int i = 0; i < n; i++) {
	int cur = 0, last = -1;
	for (int j = 0; j < m; j++) {
	if (a1[i] == a2[j]) {
	if (cur + 1 > table[j]) {
	table[j] = cur + 1;
	parent[j] = last;
	}
	}
	if (a1[i] > a2[j]) {
	if (table[j] > cur) {
	cur = table[j];
	last = j;
	}
	}
	}
	}
	int ans = 0, idx = -1;
	for (int i = 0; i < m; i++) {
	if (table[i] > ans) {
	ans = table[i];
	idx = i;
	}
	}
	vector<int> v(ans);
	for (int i = 0; idx != -1; i++) {
	v[i] = a2[idx];
	idx = parent[idx];
	}
	cout << "The LCIS is:";
	for (int i = ans - 1; i >= 0; i--) cout << " " << v[i];
	cout << endl;
	return ans;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int a1[] = {3, 4, 9, 1};
	int a2[] = {5, 3, 8, 9, 10, 2, 1};
	int n = sizeof(a1) / sizeof(a1[0]);
	int m = sizeof(a2) / sizeof(a2[0]);
	cout << LCIS(a1, n, a2, m);
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw LCIS.cpp hosted with ❤ by GitHub

	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 100005
	#define tc printf("Case %d: ", cs)
	#define tcn printf("Case %d:\n", cs);
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	#define dbg(x) cerr << #x << " = " << x << endl;
	#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
	#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
	int lis(vector<int>& v, int n)
	{
	if ((int)v.size() == 0) return 0;
	vector<int> tail(n, 0);
	int len = 1;
	tail[0] = v[0];
	for (int i = 0; i < n; i++) {
	if (v[i] > tail[len - 1])
	tail[len++] = v[i];
	else {
	auto it = find(tail.begin(), tail.begin() + len, v[i]);
	if (it != tail.begin() + len) continue;
	// this element not present in the tail
	it = upper_bound(tail.begin(), tail.begin() + len, v[i]);
	*it = v[i];
	}
	}
	return len;
	}
	const int nx = 10005;
	void lis_with_multiset(int a[], int n)
	{
	multiset<int> lis;
	for (int i = 0; i < n; i++) {
	lis.insert(a[i]);
	auto it = lis.upper_bound(a[i]);
	if (it != lis.end()) lis.erase(it);
	}
	cout << lis.size() << endl;
	}
	int main()
	{
	FASTIO
	///*
	//double start_time = clock();
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int ar[] = {2, 5, 3, 7, 11, 8, 10, 13, 6};
	int n = sizeof(ar) / sizeof(ar[0]);
	vector<int> v(n);
	for (int i = 0; i < n; i++) v[i] = ar[i];
	cout << lis(v, n) << endl;
	lis_with_multiset(ar, n);
	//double end_time = clock();
	//printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
	return 0;
	}

view raw lis.cpp hosted with ❤ by GitHub

Share: