← Back to DSA Course | Chapter 14: Dynamic Programming | Lesson 7 of 12

Longest Increasing Subsequence क्या है

Longest increasing subsequence एक list से numbers की सबसे लंबी chain पिक करने जैसा है जो बड़े होते रहते हैं, जो fit न हों उन्हें skip करते हुए।

In this page:

  1. LIS Idea
  2. DP State
  3. Transition
  4. Reconstruction
  5. Practice
Syntax
markup 
dp = [1] * len(arr)
for i in range(len(arr)):
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)
answer = max(dp)

LIS Idea

किसी array का longest increasing subsequence elements की सबसे लंबी run है, ज़रूरी नहीं adjacent हों, जो original array में left से right पढ़ते समय strictly value में बढ़ता रहे।

उदाहरण: LIS Idea

#include <iostream>
using namespace std;
int main() {
	int arr[] = {3,1,4,1,5,9,2,6};
	cout << "Longest strictly increasing run (not necessarily adjacent): 1,4,5,9 has length 4";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {3,1,4,1,5,9,2,6};
		System.out.println("Longest strictly increasing run (not necessarily adjacent): 1,4,5,9 has length 4");
	}
}
arr = [3,1,4,1,5,9,2,6]
print("Longest strictly increasing run (not necessarily adjacent): 1,4,5,9 has length 4")
#include <stdio.h>
int main() {
	int arr[] = {3,1,4,1,5,9,2,6};
	printf("Longest strictly increasing run (not necessarily adjacent): 1,4,5,9 has length 4");
	return 0;
}

DP State

dp[i] उस longest increasing subsequence की length store करता है जो बिल्कुल index i पर खत्म होता है, इसलिए overall answer बस dp array में कहीं भी मिली सबसे बड़ी value है एक बार यह पूरी तरह compute हो जाए।

उदाहरण: DP State

#include <iostream>
using namespace std;
int main() {
	int arr[] = {3,1,4,1,5,9,2,6};
	int dp[8]; for (int i=0;i<8;i++) dp[i]=1;
	cout << "dp[i] = LIS length ending exactly at index i, initialized to 1 (each element alone)";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {3,1,4,1,5,9,2,6};
		int[] dp = new int[8];
		java.util.Arrays.fill(dp, 1);
		System.out.println("dp[i] = LIS length ending exactly at index i, initialized to 1 (each element alone)");
	}
}
arr = [3,1,4,1,5,9,2,6]
dp = [1] * 8
print("dp[i] = LIS length ending exactly at index i, initialized to 1 (each element alone)")
#include <stdio.h>
int main() {
	int arr[] = {3,1,4,1,5,9,2,6};
	int dp[8]; for (int i=0;i<8;i++) dp[i]=1;
	printf("dp[i] = LIS length ending exactly at index i, initialized to 1 (each element alone)");
	return 0;
}

Transition

हर index i के लिए, आप हर पहले index j को वापस देखते हैं: अगर j पर value i पर value से छोटी हो, index i उस subsequence को extend कर सकता है, इसलिए dp[i] उन सभी valid j में से सबसे बड़ा dp[j] + 1 बन जाता है।

उदाहरण: Transition

#include <iostream>
using namespace std;
int main() {
	int arr[] = {3,1,4,1,5,9,2,6};
	int dp[8]; for (int i=0;i<8;i++) dp[i]=1;
	int best = 1;
	for (int i = 1; i < 8; i++) {
		for (int j = 0; j < i; j++)
			if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j]+1);
		best = max(best, dp[i]);
	}
	cout << "Longest increasing subsequence length: " << best;
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {3,1,4,1,5,9,2,6};
		int[] dp = new int[8];
		java.util.Arrays.fill(dp, 1);
		int best = 1;
		for (int i = 1; i < 8; i++) {
			for (int j = 0; j < i; j++)
				if (arr[j] < arr[i]) dp[i] = Math.max(dp[i], dp[j]+1);
			best = Math.max(best, dp[i]);
		}
		System.out.println("Longest increasing subsequence length: " + best);
	}
}
arr = [3,1,4,1,5,9,2,6]
dp = [1]*8
best = 1
for i in range(1, 8):
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j]+1)
    best = max(best, dp[i])
print("Longest increasing subsequence length:", best)
#include <stdio.h>
int main() {
	int arr[] = {3,1,4,1,5,9,2,6};
	int dp[8]; for (int i=0;i<8;i++) dp[i]=1;
	int best = 1;
	for (int i = 1; i < 8; i++) {
		for (int j = 0; j < i; j++)
			if (arr[j] < arr[i] && dp[j]+1 > dp[i]) dp[i] = dp[j]+1;
		if (dp[i] > best) best = dp[i];
	}
	printf("Longest increasing subsequence length: %d", best);
	return 0;
}

Reconstruction

हर dp[i] किस पहले index से extend हुआ यह track रखना आपको best ending index से पीछे चलने और असली values का sequence rebuild करने देता है, सिर्फ यह report करने के बजाय कि यह कितना लंबा है।

उदाहरण: Reconstruction

#include <iostream>
using namespace std;
int main() {
	int arr[] = {3,1,4,1,5};
	int dp[5], from[5];
	for (int i=0;i<5;i++) { dp[i]=1; from[i]=-1; }
	for (int i = 1; i < 5; i++)
		for (int j = 0; j < i; j++)
			if (arr[j] < arr[i] && dp[j]+1 > dp[i]) { dp[i]=dp[j]+1; from[i]=j; }
	cout << "from[] lets you walk backward from the best-ending index to rebuild the actual sequence";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] arr = {3,1,4,1,5};
		int[] dp = new int[5], from = new int[5];
		java.util.Arrays.fill(dp, 1);
		java.util.Arrays.fill(from, -1);
		for (int i = 1; i < 5; i++)
			for (int j = 0; j < i; j++)
				if (arr[j] < arr[i] && dp[j]+1 > dp[i]) { dp[i]=dp[j]+1; from[i]=j; }
		System.out.println("from[] lets you walk backward from the best-ending index to rebuild the actual sequence");
	}
}
arr = [3,1,4,1,5]
dp = [1]*5
frm = [-1]*5
for i in range(1, 5):
    for j in range(i):
        if arr[j] < arr[i] and dp[j]+1 > dp[i]:
            dp[i] = dp[j]+1
            frm[i] = j
print("from[] lets you walk backward from the best-ending index to rebuild the actual sequence")
#include <stdio.h>
int main() {
	int arr[] = {3,1,4,1,5};
	int dp[5], from[5];
	for (int i=0;i<5;i++) { dp[i]=1; from[i]=-1; }
	for (int i = 1; i < 5; i++)
		for (int j = 0; j < i; j++)
			if (arr[j] < arr[i] && dp[j]+1 > dp[i]) { dp[i]=dp[j]+1; from[i]=j; }
	printf("from[] lets you walk backward from the best-ending index to rebuild the actual sequence");
	return 0;
}

Practice

LIS-style reasoning nested boxes की longest chain ढूंढने या non-decreasing stock trades के best sequence जैसी problems में दिखता है, कहीं भी जहां आपको किसी बड़े sequence के अंदर छुपा longest valid ordering चाहिए।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "LIS reasoning: longest chain of nested boxes, best sequence of non-decreasing stock trades";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("LIS reasoning: longest chain of nested boxes, best sequence of non-decreasing stock trades");
	}
}
print("LIS reasoning: longest chain of nested boxes, best sequence of non-decreasing stock trades")
#include <stdio.h>
int main() {
	printf("LIS reasoning: longest chain of nested boxes, best sequence of non-decreasing stock trades");
	return 0;
}
Related Topics

Longest Common Subsequence क्या है · Edit Distance क्या है · Unbounded Knapsack समस्या · Coin Change समस्या

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. dp[i] को 1 के बजाय 0 सेट करना, क्योंकि हर element अकेला length 1 का एक subsequence है।
  2. सभी dp[i] के maximum के बजाय dp[n - 1] return करना।
  3. Comparison में <= उपयोग करना जब subsequence को strictly increasing होना चाहिए।
🔒

Chapter Quiz — Complete all 12 topics to unlock

0/12 topics done

Complete these topics first:

← Previous Lesson Longest Common Subsequence Next Lesson → Edit Distance

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.