[Feature]: Add Longest Increasing Subsequence (LIS) Dynamic Programming Visualizer

[ADARSHsri2004]

So, what is it about?

Description

Implement a Dynamic Programming visualizer for the Longest Increasing Subsequence (LIS) problem.
This will allow users to step through each DP state update interactively and understand how the algorithm builds the solution.

---

About the Algorithm

Problem Statement:
Given an array arr[] of size n, find the length of the longest subsequence such that all elements of the subsequence are in increasing order.

DP Approach (O(n²)):

• State:
  dp[i] → length of LIS ending at index i

• Transition:
  For every j < i,
  if arr[j] < arr[i], then
  dp[i] = max(dp[i], dp[j] + 1)

• Base Case:
  dp[i] = 1 for all i

• Answer:
  max(dp[i]) for all i

---

Planned Visualization Steps

1. DP Table Initialization:

   • Display array elements horizontally.
   • Initialize all dp[i] = 1 visually.

2. Transition Updates:

   • Highlight arr[j] and arr[i] pairs being compared.
   • If arr[j] < arr[i], show the update
     dp[i] = max(dp[i], dp[j] + 1)
     with animation or color change.

3. Step-through Mode:

   • Animate each comparison step to show how the LIS length is updated gradually.

4. Final Output:

   • Highlight the cells forming the final LIS sequence.
   • Display the computed LIS length.

---

Planned Features

• DP table visualization (animated state updates)
• Subproblem tracing (j → i comparisons)
• State transition explanation below the visualization
• Replay / pause controls for better understanding

---

Tech Stack

• Frontend: React + TypeScript
• UI Library: Tailwind / Shadcn UI
• Animation: Framer Motion
• Algorithm Logic: Pure JS/TS (state-based DP updates)

---

Expected Outcome

A fully interactive visual explanation of the Longest Increasing Subsequence (LIS) problem, helping users understand:

• How subproblems relate
• How DP states evolve
• Why the final LIS length is correct

---

My Approach

I plan to:

• Use a color-coded DP table to show transitions visually.
• Highlight comparisons between arr[j] and arr[i] dynamically.
• Use Framer Motion for smooth step transitions.
• Provide tooltips or captions explaining each DP update in real time.
• Allow users to move forward or backward through DP states interactively.

Code of Conduct

• I agree to follow this project's Code of Conduct

[LONECODER1]

@adityacosmos24 if not yet resolved, can you assign it to me

[adityacosmos24]

@LONECODER1 assigned