DP Optimization(Part-4) | Longest Increasing Subsequence | DP Series(Episode-18)

 এই পর্বে আমরা মূলত ডাটা স্ট্রাকচার ব্যাবহারের মাধ্যমে কিছু কিছু ডিপি প্রব্লেমের কমপ্লেক্সিটি কিভাবে কমিয়ে আনা সম্ভব তা দেখবো। 

Problem:

মনে কর, তোমাকে একটি n<=10^4 সাইজের অ্যারে দেয়া আছে। এই অ্যারের দীর্ঘতম ক্রমবর্ধমান অনুক্রমের দৈর্ঘ্য বের করতে হবে😛

ইংরেজীতে বললে Longest Increasing Subsequence এর Length বের করতে হবে। তাহলে এই প্রব্লেমের সল্যুশন কি হতে পারে? 

Hints: শেষ থেকে শুরুর দিকে প্রত্যেক পজিশনে দাঁড়িয়ে দেখবো এই পজিশনের ভ্যালুটি অবশ্যই নিলে আমি সর্বোচ্চ কত লেন্থ এর LIS বানাতে পারবো। এভাবে সবগুলো রেজাল্ট এর মধ্যে ম্যাক্সিমাম টা এন্সার। 

কোডটি হলোঃ 

	#include<bits/stdc++.h>
	using namespace std;
	int n,ara[10005],dp[10005];
	/** Here, dp[i] means if I must take the ith element, then what will be the
	LIS considering ith to nth element **/
	void FuN()
	{
	int ans = 0;
	for(int i=n ; i>=1 ; i--){
	dp[i] = 1;
	int mx = 0;
	for(int j=i+1 ; j<=n ; j++){
	if(ara[j] >= ara[i])
	mx = max(mx , dp[j]);
	}
	dp[i] += mx;
	ans = max(ans , dp[i]);
	}
	cout<<ans<<endl;
	}
	int main()
	{
	cin>>n;
	for(int i=1 ; i<=n ; i++) cin>>ara[i];
	FuN();
	return 0;
	}

view raw Optimized DP-4.1.cpp hosted with ❤ by GitHub

এখন, কী হবে যদি n<=10^5 এবং a[i]<=10^5 হয়? 

উপরের সল্যুশন এ ভালো করে লক্ষ্য করলে দেখবে যে, প্রত্যেক পজিশন i তে দাঁড়িয়ে আমরা দেখি i এর ডানে যেসব ভ্যালু আছে a[i] এর সমান অথবা বড় তাদের মধ্যে কার DP এর ভ্যালু সর্বোচ্চ? যেখানে, dp[i] বলতে বোঝায় ith to nth ইনডেক্সের ভ্যালুগুলো কনসিডার করে সর্বোচ্চ কত লেন্থ এর LIS বানানো যায়। 

একটু ভালো করে চিন্তা করলে দেখবে ১৫ নম্বর লাইনের ইনার লুপের কাজ আমরা সেগমেন্ট ট্রি এর একটি কুয়েরী আর আপডেট অপারেশন দ্বারা প্রতিস্থাপন করে দিতে পারি! যার ফলে আমাদের মোট কমপ্লেক্সিটি দাঁড়াবে n * log(n) ।

আমরা যখন কোন পজিশনের জন্য dp[i] বা LIS ক্যালকুলেট করবো তখন আমরা সেগমেন্ট ট্রি এর a[i] তম ইন্ডেক্সের ভ্যালু বানিয়ে দিবো dp[i] !!!  আর যেহেতু আমি শেষ থেকে শুরুর দিকে লুপ চালিয়ে ক্যালকুলেট করে যাচ্ছি সেহেতু এখন আমি i পজিশনে থাকা মানে i to nপর্যন্ত পজিশন গুলোর dp[i] ভ্যালুই সেগমেন্ট ট্রি তে আছে। 

তার মানে আমি যদি a[i] কে অবশ্যই নিয়ে সিকুয়েন্স বানাতে চাই সেক্ষেত্রে আমার জানতে হবে সেগমেন্ট ট্রি এর [ a[i] , 10^5 ] ইনডেক্স পর্যন্ত যেসব ভ্যালু আছে তাদের মধ্যে ম্যাক্সিমাম কত! 

এখনো না বুঝে থাকলে কোড দেখতে পারো। 

	#include<bits/stdc++.h>
	using namespace std;
	#define sz 100005
	int n,ara[sz],dp[sz],tree[4*sz];
	void Update(int node,int b,int e,int pos,int val)
	{
	if(pos<b || pos>e)
	return;
	if(b==pos && e==pos){
	tree[node] = val;
	return;
	}
	int mid = (b+e)>>1;
	Update(node<<1 , b , mid , pos , val);
	Update(1+(node<<1) , mid+1 , e , pos , val);
	tree[node] = max(tree[node<<1] , tree[1+(node<<1)]);
	}
	int Query(int node,int b,int e,int i,int j)
	{
	if(e<i || b>j)
	return 0;
	if(b>=i && e<=j)
	return tree[node];
	int mid = (b+e)>>1;
	int p1 = Query(node<<1 , b , mid , i , j);
	int p2 = Query(1+(node<<1) , mid+1 , e , i , j);
	return max(p1 , p2);
	}
	void FuN()
	{
	int LIS = 0;
	for(int i=n ; i>=1 ; i--){
	dp[i] = 1;
	int mx = Query(1 , 1 , 1e5 , ara[i] , 1e5);
	dp[i] += mx;
	LIS = max(LIS , dp[i]);
	Update(1 , 1 , 1e5 , ara[i] , dp[i]);
	}
	cout<<LIS<<endl;
	}
	int main()
	{
	cin>>n;
	for(int i=1 ; i<=n ; i++) cin>>ara[i];
	FuN();
	return 0;
	}

view raw Optimized DP-4.2.cpp hosted with ❤ by GitHub

এখন চিন্তা কর যদি a[i] <= 10^9 হতো? 

সিম্পল! অ্যারে কম্প্রেশন করতাম সেক্ষেত্রে।

এখন, আমরা LIS বের করার আরো একটি কোড দেখবোঃ 

	#include<bits/stdc++.h>
	using namespace std;
	int LIS(vector<int> &v)
	{
	multiset<int>st;
	for(int i=0 ; i<(int)v.size() ; i++){
	auto it = st.lower_bound(v[i]); ///Use upper bound if u want non-decreasing sub sequence
	if(it != st.end())
	st.erase(it);
	st.insert(v[i]);
	}
	return (int)st.size();
	}
	int main()
	{
	vector<int>v = {1 , 1 , 3 , 3 , 2 , 5};
	cout<<LIS(v)<<endl;
	return 0;
	}

view raw LIS Short.cpp hosted with ❤ by GitHub

এই কোডের কমপ্লেক্সিটিও কিন্তু O(n log(n)) এবং এই কোড আগের কোডের তুলনায় অনেক ছোট!!! 

Suggested Problem here

Bonus Problem: Click here

Next Episode

Happy Coding😊