Software Engineer

Find the MST.
Identify the shortest edge not included in the MST.
Remove the longest edge from the MST.
Find the shortest path between the endpoints of the removed edge.
Combine the shortest path with the removed edge to get the second shortest path.

Problem Definition: Given an array of integers, we aim to find the length of the longest increasing subsequence.

Dynamic Programming State: Define a dynamic programming state, dp[i], where dp[i] represents the length of the longest increasing subsequence ending at index i.

Recurrence Relation: Iterate over all indices j before i and check if nums[i] > nums[j]. If it is, extend the longest increasing subsequence ending at index j by including nums[i]. Update dp[i] as max(dp[j] + 1, dp[i]).

Base Case: Initialize the dp array with all elements set to 1, as the minimum length of any subsequence is 1.

Build DP Table: Iterate over the array and compute the dp array using the recurrence relation defined in step 3.

Find Maximum Length: Once the dp array is built, the length of the longest increasing subsequence will be the maximum value in the dp array.

Return Result: Return the maximum value found in the dp array, which represents the length of the longest increasing subsequence.

Tip 1: Give the brute force approach
Tip 2: Solve all the corner cases 
Tip 3: Optimised the solution