Learned Dynamic Programming with GeeksforGeeks LIS problem

🚀 Day 110 of #100DaysOfCode ✅ Topic: Dynamic Programming — Longest Increasing Subsequence (LIS) 💡 Platform: GeeksforGeeks (Problem: Longest Increasing Subsequence) 🧠 Concept Learned: Today I practiced Dynamic Programming (DP) to find the length of the longest strictly increasing subsequence in an array. A subsequence is different from a subarray — elements need not be contiguous, only in increasing order. 📘 Approach Used: Initialize an array lis[] where lis[i] stores the length of the LIS ending at index i. For every element, check all previous elements to see if arr[i] > arr[prev]. If yes, update: lis[i] = max(lis[i], lis[prev] + 1) The final answer is max(lis) — the length of the longest subsequence. 🧩 Example: Input: arr = [5, 8, 3, 7, 9, 1] Output: 3 (Longest Increasing Subsequence → [5, 7, 9]) ✅ Result: All test cases passed (1111 / 1111) 🎯 Understood how Dynamic Programming helps break down complex problems into smaller overlapping subproblems efficiently.

  • graphical user interface, text, application

To view or add a comment, sign in

Explore content categories