Scriba — test_reference

Step 1 / 13

Array $a = [3,1,4,1,5]$ . We compute $dp[i]$ = LIS length ending at index $i$ .

Step 2 / 13

Base case: $dp[0] = 1$ . All others start unknown.

Step 3 / 13

Start scanning from index 0. The cursor highlights the current cell.

Step 4 / 13

Move cursor to index 1. Previous cell marked done.

Step 5 / 13

Move cursor to index 2.

Step 6 / 13

$dp[2] = 2$ : we can extend from $dp[0]$ since $a[0]=3 < a[2]=4$ .

Step 7 / 13

$dp[3] = 1$ : no previous element is smaller than $a[3]=1$ .

Step 8 / 13

$dp[4] = 3$ : extend from $dp[2]$ since $a[2]=4 < a[4]=5$ .

Step 9 / 13

Mark even-indexed elements. The LIS length is 3.

Step 10 / 13

Traceback: highlight the optimal LIS path in the DP table.

Step 11 / 13

Recolor transition arrows along the optimal path.

Step 12 / 13

Let us verify the sub-problem for index 2 in detail.

Compare $a[0]=3$ with $a[2]=4$ : since $3 < 4$ , we can extend.

Confirmed: $dp[2] = dp[0] + 1 = 2$ .

Step 13 / 13

Final answer at index $ ${target\_idx} = 4$ : LIS length is $dp[4] = 3$ .

test_reference_advanced