The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

# Problem statement
**The *Longest Increasing Subsequence* (LIS) problem requires you to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.**

For example, the length of LIS for `{10, 9, 3, 5, 4, 11, 7, 8}` is `4` and LIS is `{3, 4, 7, 8}`.

# Solution: **Naïve approach**
The simplest approach is to try to find all increasing subsequences and then returning the maximum length of the longest increasing subsequence. 

* Time complexity : *O(${2^n}$)* 
* Space complexity : *O(${2^n}$)*

Since the complexity is going to be exponential once again, we need an optimized solution. We can solve this problem using the dynamic programming approach.

# Solution: **Dynamic programming**
Before moving on to the implementation, let’s look at the recurrence relation.
* Let `arr[0..n-1]` be the input array and `LIS(i)` be the length of the LIS ending at index `i` such that `arr[i]` is the last element of the LIS.
* `LIS(i) = 1 + max{ LIS(j) }` where `0 < j < i` and `arr[j] < arr[i]`
* `LIS(i) = 1`, if no such `j` exists
* To find the LIS for a given array, we need to return `max(LIS(i))`, where `0 < i < n`.

Formally, the length of the longest increasing subsequence ending at index `i` will be `1` greater than the maximum of lengths of all longest increasing subsequences ending at indices before `i`, where `arr[j] < arr[i] (j < i)`. Thus, we see that the LIS problem satisfies the optimal substructure property as the main problem can be solved using solutions to subproblems.

Let’s move on to the implementation now.

Learn about another variation of the string-based problems that are solved using dynamic programming.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

Longest Increasing Subsequence

Problem statement

Solution: Naïve approach