Longest Increasing Subsequence in DSA Java - Execution Trace

Concept Flow - Longest Increasing Subsequence

Start with array

↓

Initialize LIS array with 1s

↓

For each element i from 1 to n-1

↓

For each element j from 0 to i-1

↓

Check if arr[i

↓

Update LIS[i

↓

Repeat inner loop

↓

Repeat outer loop

↓

Find max value in LIS array

↓

Return max LIS length

We start with the array and build an LIS array where each position stores the length of the longest increasing subsequence ending there. We update LIS values by comparing current elements with previous ones. Finally, we find the maximum LIS length.

Execution Sample

DSA Java

int[] arr = {10, 22, 9, 33, 21, 50, 41, 60};
int[] lis = new int[arr.length];
for (int i = 0; i < arr.length; i++) lis[i] = 1;
for (int i = 1; i < arr.length; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j] && lis[i] < lis[j] + 1) lis[i] = lis[j] + 1;
  }
}
int max = 1;
for (int i = 0; i < lis.length; i++) if (lis[i] > max) max = lis[i];
System.out.println(max);

This code calculates the length of the longest increasing subsequence in the array.

Execution Table

Step	Operation	i	j	Condition arr[i] > arr[j]	Condition lis[i] < lis[j] + 1	LIS Array State	Max LIS So Far
1	Initialize LIS array	-	-	-	-	[1, 1, 1, 1, 1, 1, 1, 1]	1
2	i=1, j=0 check	1	0	22 > 10 (True)	1 < 1 + 1 (True)	[1, 2, 1, 1, 1, 1, 1, 1]	2
3	i=2, j=0 check	2	0	9 > 10 (False)	-	[1, 2, 1, 1, 1, 1, 1, 1]	2
4	i=2, j=1 check	2	1	9 > 22 (False)	-	[1, 2, 1, 1, 1, 1, 1, 1]	2
5	i=3, j=0 check	3	0	33 > 10 (True)	1 < 1 + 1 (True)	[1, 2, 1, 2, 1, 1, 1, 1]	2
6	i=3, j=1 check	3	1	33 > 22 (True)	2 < 2 + 1 (True)	[1, 2, 1, 3, 1, 1, 1, 1]	3
7	i=3, j=2 check	3	2	33 > 9 (True)	3 < 1 + 1 (False)	[1, 2, 1, 3, 1, 1, 1, 1]	3
8	i=4, j=0 check	4	0	21 > 10 (True)	1 < 1 + 1 (True)	[1, 2, 1, 3, 2, 1, 1, 1]	3
9	i=4, j=1 check	4	1	21 > 22 (False)	-	[1, 2, 1, 3, 2, 1, 1, 1]	3
10	i=4, j=2 check	4	2	21 > 9 (True)	2 < 1 + 1 (False)	[1, 2, 1, 3, 2, 1, 1, 1]	3
11	i=4, j=3 check	4	3	21 > 33 (False)	-	[1, 2, 1, 3, 2, 1, 1, 1]	3
12	i=5, j=0 check	5	0	50 > 10 (True)	1 < 1 + 1 (True)	[1, 2, 1, 3, 2, 2, 1, 1]	3
13	i=5, j=1 check	5	1	50 > 22 (True)	2 < 2 + 1 (True)	[1, 2, 1, 3, 2, 3, 1, 1]	3
14	i=5, j=2 check	5	2	50 > 9 (True)	3 < 1 + 1 (False)	[1, 2, 1, 3, 2, 3, 1, 1]	3
15	i=5, j=3 check	5	3	50 > 33 (True)	3 < 3 + 1 (True)	[1, 2, 1, 3, 2, 4, 1, 1]	4
16	i=5, j=4 check	5	4	50 > 21 (True)	4 < 2 + 1 (False)	[1, 2, 1, 3, 2, 4, 1, 1]	4
17	i=6, j=0 check	6	0	41 > 10 (True)	1 < 1 + 1 (True)	[1, 2, 1, 3, 2, 4, 2, 1]	4
18	i=6, j=1 check	6	1	41 > 22 (True)	2 < 2 + 1 (True)	[1, 2, 1, 3, 2, 4, 3, 1]	4
19	i=6, j=2 check	6	2	41 > 9 (True)	3 < 1 + 1 (False)	[1, 2, 1, 3, 2, 4, 3, 1]	4
20	i=6, j=3 check	6	3	41 > 33 (True)	3 < 3 + 1 (True)	[1, 2, 1, 3, 2, 4, 4, 1]	4
21	i=6, j=4 check	6	4	41 > 21 (True)	4 < 2 + 1 (False)	[1, 2, 1, 3, 2, 4, 4, 1]	4
22	i=6, j=5 check	6	5	41 > 50 (False)	-	[1, 2, 1, 3, 2, 4, 4, 1]	4
23	i=7, j=0 check	7	0	60 > 10 (True)	1 < 1 + 1 (True)	[1, 2, 1, 3, 2, 4, 4, 2]	4
24	i=7, j=1 check	7	1	60 > 22 (True)	2 < 2 + 1 (True)	[1, 2, 1, 3, 2, 4, 4, 3]	4
25	i=7, j=2 check	7	2	60 > 9 (True)	3 < 1 + 1 (False)	[1, 2, 1, 3, 2, 4, 4, 3]	4
26	i=7, j=3 check	7	3	60 > 33 (True)	3 < 3 + 1 (True)	[1, 2, 1, 3, 2, 4, 4, 4]	4
27	i=7, j=4 check	7	4	60 > 21 (True)	4 < 2 + 1 (False)	[1, 2, 1, 3, 2, 4, 4, 4]	4
28	i=7, j=5 check	7	5	60 > 50 (True)	4 < 4 + 1 (True)	[1, 2, 1, 3, 2, 4, 4, 5]	5
29	i=7, j=6 check	7	6	60 > 41 (True)	5 < 4 + 1 (False)	[1, 2, 1, 3, 2, 4, 4, 5]	5
30	Find max LIS	-	-	-	-	[1, 2, 1, 3, 2, 4, 4, 5]	5

💡 All elements processed; max LIS length found as 5

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 15	After Step 20	After Step 28	Final
i	-	1	3	5	6	7	-
j	-	0	1	4	5	6	-
LIS	[1,1,1,1,1,1,1,1]	[1,2,1,1,1,1,1,1]	[1,2,1,3,1,1,1,1]	[1,2,1,3,2,4,1,1]	[1,2,1,3,2,4,4,1]	[1,2,1,3,2,4,4,5]	[1,2,1,3,2,4,4,5]
Max LIS	1	2	3	4	4	5	5

Key Moments - 3 Insights

Why do we initialize the LIS array with 1s at the start?

Each element alone is an increasing subsequence of length 1, so LIS starts with 1 for all. See Step 1 in execution_table.

Why do we check both conditions arr[i] > arr[j] and lis[i] < lis[j] + 1 before updating LIS[i]?

We only update LIS[i] if arr[i] can extend an increasing subsequence ending at j (arr[i] > arr[j]) and if this extension makes LIS[i] longer than before. See Steps 2, 6, and 15.

How do we find the final longest increasing subsequence length?

After filling LIS array, the maximum value in it is the length of the longest increasing subsequence. See Step 30.

Visual Quiz - 3 Questions

Look at the execution_table at Step 15, what is the LIS array state?

A [1, 2, 1, 3, 2, 4, 1, 1]

B [1, 2, 1, 3, 2, 3, 1, 1]

C [1, 2, 1, 3, 2, 4, 4, 1]

D ]1 ,1 ,4 ,2 ,3 ,1 ,2 ,1[

💡 Hint

Check the LIS Array State column at Step 15 in execution_table.

At which step does the max LIS value first become 4?

A Step 6

B Step 15

C Step 20

D Step 28

💡 Hint

Look at the Max LIS So Far column in execution_table.

If the array had all equal elements, how would the LIS array look after initialization and updates?

A All 1s throughout

B Increasing values from 1 to n

C Zeros after initialization

D Random values

💡 Hint

Refer to key_moments about LIS initialization and condition checks.

Concept Snapshot

Longest Increasing Subsequence (LIS):
- Initialize LIS array with 1s (each element alone)
- For each element i, check all previous j < i
- If arr[i] > arr[j] and LIS[i] < LIS[j] + 1, update LIS[i]
- Max value in LIS array is the length of LIS
- Time complexity: O(n^2)

Full Transcript

The Longest Increasing Subsequence problem finds the longest sequence of increasing numbers in an array. We start by creating an array LIS where each element is 1, meaning each element is a subsequence of length 1 by itself. Then for each element i, we look at all previous elements j. If arr[i] is greater than arr[j] and extending the subsequence ending at j makes LIS[i] longer, we update LIS[i]. After processing all elements, the maximum value in LIS is the length of the longest increasing subsequence. This process is shown step-by-step in the execution table, tracking how LIS array changes and how the max LIS value updates. This approach takes O(n^2) time because of the nested loops.

Practice

1. What does the Longest Increasing Subsequence (LIS) problem ask for in a given sequence of numbers?

easy

A. The longest subsequence with all equal numbers

B. The longest subsequence where each number is smaller than the previous one

C. The longest subsequence with alternating increasing and decreasing numbers

D. The longest subsequence where each number is larger than the previous one

Solution

1. Step 1: Understand the problem definition

   The Longest Increasing Subsequence is a subsequence where every next number is strictly greater than the previous one.

2. Step 2: Compare options with the definition

   The longest subsequence where each number is larger than the previous one matches the definition exactly, while others describe different patterns.

3. Final Answer:

   The longest subsequence where each number is larger than the previous one -> Option D

4. Quick Check:

   LIS = strictly increasing subsequence [OK]

Hint: Look for strictly increasing order in subsequence [OK]

Common Mistakes:

• Confusing subsequence with substring
• Thinking LIS means non-decreasing instead of strictly increasing
• Mixing up increasing with decreasing sequences

2. Which of the following Java code snippets correctly initializes an array to store the length of LIS ending at each index for an input array arr of size n?

easy

A. int[] lis = new int[n]; lis.fill(1);

B. int[] lis = new int[n]; for(int i=0; i

C. int[] lis = new int[n]; for(int i=0; i

D. int lis[] = new int[n]; Arrays.fill(lis, 0);

Solution

1. Step 1: Understand LIS initialization

   Each element starts with LIS length 1 because the smallest subsequence is the element itself.

2. Step 2: Check code correctness

   int[] lis = new int[n]; for(int i=0; ifill on array. int lis[] = new int[n]; Arrays.fill(lis, 0); fills with 0, incorrect for LIS.

3. Final Answer:

   int[] lis = new int[n]; for(int i=0; i -> Option C

4. Quick Check:

   Initialize LIS array with 1s [OK]

Hint: Initialize LIS array with 1 for each element [OK]

Common Mistakes:

• Initializing LIS array with zeros
• Using non-existent array methods like fill()
• Not initializing LIS array before DP

3. What is the output of the following Java code snippet that calculates the length of the Longest Increasing Subsequence for the array arr = {10, 22, 9, 33, 21, 50, 41, 60}?

int[] arr = {10, 22, 9, 33, 21, 50, 41, 60};
int n = arr.length;
int[] lis = new int[n];
for (int i = 0; i < n; i++) lis[i] = 1;
for (int i = 1; i < n; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = 0;
for (int i = 0; i < n; i++) {
  if (lis[i] > max) max = lis[i];
}
System.out.println(max);

medium

A. 5

B. 4

C. 6

D. 3

Solution

1. Step 1: Calculate LIS array values

   For each element, find LIS ending there: - arr[0]=10: lis=1 - arr[1]=22 >10: lis=2 - arr[2]=9: lis=1 - arr[3]=33 >22: lis=3 - arr[4]=21 >10 but <22: lis=2 - arr[5]=50 >33: lis=4 - arr[6]=41 >33 but <50: lis=4 - arr[7]=60 >50: lis=5

2. Step 2: Find max LIS length

   Maximum value in lis array is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Max LIS length = 5 [OK]

Hint: Trace LIS array updates step-by-step [OK]

Common Mistakes:

• Confusing subsequence length with subarray length
• Not updating lis[i] correctly inside nested loops
• Forgetting to find max LIS after filling array

4. Identify the bug in the following Java code snippet that attempts to compute the length of the Longest Increasing Subsequence for array arr:

int[] lis = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
  lis[i] = 0;
}
for (int i = 1; i < arr.length; i++) {
  for (int j = 0; j < i; j++) {
    if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
      lis[i] = lis[j] + 1;
    }
  }
}
int max = 0;
for (int i = 0; i < lis.length; i++) {
  if (lis[i] > max) max = lis[i];
}
System.out.println(max);

medium

A. LIS array should be initialized with 1, not 0

B. The inner loop should start from i+1 instead of 0

C. The comparison should be arr[i] < arr[j] instead of arr[i] > arr[j]

D. The max variable should be initialized to Integer.MIN_VALUE

Solution

1. Step 1: Check LIS array initialization

   LIS array must start with 1 for each element because each element alone forms a subsequence of length 1. Initializing with 0 causes incorrect LIS lengths.

2. Step 2: Verify loops and conditions

   Inner loop and comparison are correct. Max initialization to 0 is fine since LIS lengths are positive.

3. Final Answer:

   LIS array should be initialized with 1, not 0 -> Option A

4. Quick Check:

   Initialize LIS with 1 to avoid zero-length subsequences [OK]

Hint: Always start LIS array values at 1 [OK]

Common Mistakes:

• Initializing LIS array with zeros
• Changing loop ranges incorrectly
• Misunderstanding LIS condition comparison

5. Given the array arr = {3, 10, 2, 1, 20}, which of the following sequences is the Longest Increasing Subsequence (LIS)?

hard

A. [1, 2, 3]

B. [3, 10, 20]

C. [10, 20]

D. [3, 2, 1, 20]

Solution

1. Step 1: Identify increasing subsequences

   Check each option for strictly increasing order: - [3, 10, 20]: 3 < 10 < 20 (valid) - [3, 2, 1, 20]: 3 > 2 > 1 (not increasing) - [10, 20]: 10 < 20 (valid but shorter) - [1, 2, 3]: 1 < 2 < 3 (valid but not a subsequence in original order)

2. Step 2: Compare lengths of valid subsequences

   [3, 10, 20] length is 3, [10, 20] length is 2, [1, 2, 3] length is 3 but elements not in original order (subsequence must follow original order). [1, 2, 3] is invalid as subsequence because 1 comes after 3 in original array.

3. Final Answer:

   [3, 10, 20] -> Option B

4. Quick Check:

   LIS must be increasing and follow original order [OK]

Hint: Check subsequence order matches original array [OK]

Common Mistakes:

• Choosing subsequence not in original order
• Confusing increasing with non-decreasing
• Ignoring subsequence length