## Longest Increasing Subsequence

###### DESCRIPTION (credit Leetcode.com)

Given an integer array nums, write a function that returns the length of the longest increasing subsequence within the array. The subsequence does not have to be contiguous, but the elements must be strictly increasing (i.e. nums[i] < nums[j] for all i < j).

###### EXAMPLES

Input:

`nums = [8,2,4,3,6,12]`

Output:

`4`

Explanation: The longest increasing subsequence is [2,4,6,12], which has a length of 4.

Run your code to see results here

## Explanation

This solution uses **bottom-up dynamic programming** to solve the problem. We create an integer array dp of length n where n is the length of the input array nums. dp[i] is equal to length of the longest increasing subsequence ending at the i-th index of nums. Since a single element is an increasing subsequence of length 1, we initialize dp with 1 for all elements.

def longest_increasing_subsequence(nums):if not nums:return 0n = len(nums)dp = [1] * nfor i in range(1, n):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)

We then use a for-loop i to iterate over each index in the array. The body of the loop determines the correct value for dp[i].

Inside the body of the loop, we use another for-loop j to iterate over all indexes before i. If nums[i] > nums[j], we update dp[i] to be the maximum of dp[i] and dp[j] + 1. This is because the i-th element can extend the increasing subsequence ending at the j-th element by 1. (If dp[i] is already greater than dp[j] + 1, we leave it as is - a longer subsequence ending at i has already been found.)

def longest_increasing_subsequence(nums):if not nums:return 0n = len(nums)dp = [1] * nfor i in range(1, n):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)

Finally, we return the maximum value in dp as the length of the longest increasing subsequence.

## Solution

def longest_increasing_subsequence(nums):if not nums:return 0n = len(nums)dp = [1] * nfor i in range(1, n):for j in range(i):if nums[i] > nums[j]:dp[i] = max(dp[i], dp[j] + 1)return max(dp)

## Complexity Analysis

**Time Complexity**: O(n2) where n is the length of the input array nums. We use two nested for-loops to iterate over all elements in nums.
**Space Complexity**: O(n) where n is the length of the input array nums. We use an additional array dp of length n to store the length of the longest increasing subsequence ending at each index.

Loading comments...