# Dynamic Programming Challenge: Longest Increasing Subsequence

## Recommended Posts

Given an array of integers, find the length of the longest increasing subsequence. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

For example:

#include <iostream>
#include <vector>

int longestIncreasingSubsequence(const std::vector<int>& nums) {
// Your dynamic programming solution goes here.

// Return the length of the longest increasing subsequence.
}

int main() {
std::vector<int> sequence = {10, 22, 9, 33, 21, 50, 41, 60, 80};
int result = longestIncreasingSubsequence(sequence);

std::cout << "Length of the longest increasing subsequence: " << result << std::endl;

return 0;
}

I'm specifically interested in implementing this using dynamic programming techniques. How can I approach this problem using dynamic programming, and what would be the C++ code for solving it? Any insights, code snippets, or explanations would be incredibly helpful in mastering dynamic programming for this particular challenge. Thank you for your assistance!

##### Share on other sites

• 3 weeks later...

Dynamic programming generally involves breaking a large problem into subproblems that can be solved individually in this case the problem is reducible to finding the largest number in a sorted list that the next number is smaller than if no number in the list is smaller than the next number then it gets added to the list.


(No title)
#include <iostream>
#include <vector>

struct longestIncreasingSubesequencePacked {
int length = 0;
int lisLength = 0;
int lis[20][21];
};

longestIncreasingSubesequencePacked longestIncreasingSubsequence(const std::vector<int>& nums) {
int numsLength = nums.size();
int lowerBound, upperBound, lisIndex = 0;
struct longestIncreasingSubesequencePacked lisPack;

// Array of sequences where the index +1 is the length of the sequence
// 1. The lowest number found for a sequence of this length
// 2. A valid sequence of this length
lisPack.lis[0][0] = nums[0];
lisPack.lis[0][1] = nums[0];
for (int numsIndex = 1; numsIndex < numsLength; numsIndex++){
// Check if the number is larger than the largest number in the sequence and
// if it is add it to the sequence
if(nums[numsIndex] > lisPack.lis[lisPack.lisLength][0]){
lisPack.lisLength = lisPack.lisLength + 1;
lisPack.lis[lisPack.lisLength][0] = nums[numsIndex];
// To find the actual sequence
for (lisIndex = 1; lisIndex < lisPack.lisLength + 1; lisIndex++){
lisPack.lis[lisPack.lisLength][lisIndex] = lisPack.lis[lisPack.lisLength - 1][lisIndex];
}
lisPack.lis[lisPack.lisLength][lisPack.lisLength + 1] = nums[numsIndex];
continue;
} else {
// std::cout <<  nums[numsIndex] << std::endl;
lowerBound = 0;
upperBound = lisPack.lisLength;

// Find the largest number in a sorted array (lis)
// Lower than nums[numsIndex]
while (true){
int mid = (lowerBound + upperBound) / 2;

if (mid == 0) {
if (lisPack.lis[mid][0] > nums[numsIndex]) {
lisPack.lis[mid][0] = nums[numsIndex];
// To find the actual sequence
lisPack.lis[mid][1] = nums[numsIndex];
break;
}

if (lowerBound == (lisPack.lisLength - 1) && lisPack.lis[mid + 1][0] > nums[numsIndex]) {
mid = mid + 1;
lisPack.lis[mid][0] = nums[numsIndex];
// To find the actual sequence
for (lisIndex = 1; lisIndex <= mid + 1; lisIndex++){
lisPack.lis[mid][lisIndex] = lisPack.lis[mid - 1][lisIndex];
}
lisPack.lis[mid][mid + 1] = nums[numsIndex];
break;
}

}

if (lowerBound == lisPack.lisLength){

if (lisPack.lis[mid][0] > nums[numsIndex]) {
lisPack.lis[mid][0] = nums[numsIndex];
// To find the actual sequence
for (lisIndex = 1; lisIndex <= mid + 1; lisIndex++){
lisPack.lis[mid][lisIndex] = lisPack.lis[mid - 1][lisIndex];
}

lisPack.lis[mid][mid + 1] = nums[numsIndex];
break;
}

// no matches found and we reached the end
break;
}
if (lisPack.lis[mid][0] > nums[numsIndex] && lisPack.lis[mid + 1][0] > nums[numsIndex]) {
lisPack.lis[mid][0] = nums[numsIndex];

// To find the actual sequence
for (lisIndex = 1; lisIndex <= mid + 1; lisIndex++){
lisPack.lis[mid][lisIndex] = lisPack.lis[mid - 1][lisIndex];
}

lisPack.lis[mid][mid+1] = nums[numsIndex];
break;
}
if (lisPack.lis[mid][0] < nums[numsIndex]) {
lowerBound = mid + 1;
} else {
upperBound = mid;
}
}
}
}

std::cout << "--------" << std::endl;
for (int p = 0; p <= lisPack.lisLength; p++){
std::cout << lisPack.lis[p][0];
std::cout << " [";
for (lisIndex = 1; lisIndex <= p+1; lisIndex++){
if (lisIndex == p+1){
std::cout << lisPack.lis[p][lisIndex];
} else {
std::cout << lisPack.lis[p][lisIndex] << ", ";
}
}
std::cout << "]" << std::endl;
}
lisPack.length = lisPack.lisLength + 1;
return lisPack;
}

longestIncreasingSubesequencePacked longestIncreasingSubsequenceContd(const std::vector<int>& nums, struct longestIncreasingSubesequencePacked lisPack) {
int numsLength = nums.size();
int lowerBound, upperBound, lisIndex = 0;
for (int numsIndex = 0; numsIndex < numsLength; numsIndex++){

// Check if the number is larger than the largest number in the sequence and
// if it is add it to the sequence
if(nums[numsIndex] > lisPack.lis[lisPack.lisLength][0]){
lisPack.lisLength = lisPack.lisLength + 1;
lisPack.lis[lisPack.lisLength][0] = nums[numsIndex];
// To find the actual sequence
for (lisIndex = 1; lisIndex < lisPack.lisLength + 1; lisIndex++){
lisPack.lis[lisPack.lisLength][lisIndex] = lisPack.lis[lisPack.lisLength - 1][lisIndex];
}
lisPack.lis[lisPack.lisLength][lisPack.lisLength + 1] = nums[numsIndex];
continue;
} else {
// std::cout <<  nums[numsIndex] << std::endl;
lowerBound = 0;
upperBound = lisPack.lisLength;

// Find the largest number in a sorted array (lis)
// Lower than nums[numsIndex]
while (true){
int mid = (lowerBound + upperBound) / 2;

if (mid == 0) {
if (lisPack.lis[mid][0] > nums[numsIndex]) {
lisPack.lis[mid][0] = nums[numsIndex];
// To find the actual sequence
lisPack.lis[mid][1] = nums[numsIndex];
break;
}

if (lowerBound == (lisPack.lisLength - 1) && lisPack.lis[mid + 1][0] > nums[numsIndex] && lisPack.lis[mid - 1][0] < nums[numsIndex]) {
mid = mid + 1;
lisPack.lis[mid][0] = nums[numsIndex];
// To find the actual sequence
for (lisIndex = 1; lisIndex <= mid + 1; lisIndex++){
lisPack.lis[mid][lisIndex] = lisPack.lis[mid - 1][lisIndex];
}
lisPack.lis[mid][mid + 1] = nums[numsIndex];
break;
}

}

if (lowerBound == lisPack.lisLength){

if (lisPack.lis[mid][0] > nums[numsIndex]) {
lisPack.lis[mid][0] = nums[numsIndex];
// To find the actual sequence
for (lisIndex = 1; lisIndex <= mid + 1; lisIndex++){
lisPack.lis[mid][lisIndex] = lisPack.lis[mid - 1][lisIndex];
}

lisPack.lis[mid][mid + 1] = nums[numsIndex];
break;
}

// no matches found and we reached the end
break;
}
if (lisPack.lis[mid][0] > nums[numsIndex] && lisPack.lis[mid + 1][0] > nums[numsIndex] && lisPack.lis[mid - 1][0] < nums[numsIndex]) {
lisPack.lis[mid][0] = nums[numsIndex];

// To find the actual sequence
for (lisIndex = 1; lisIndex <= mid + 1; lisIndex++){
lisPack.lis[mid][lisIndex] = lisPack.lis[mid - 1][lisIndex];
}

lisPack.lis[mid][mid+1] = nums[numsIndex];
break;
}
if (lisPack.lis[mid][0] < nums[numsIndex]) {
lowerBound = mid + 1;
} else {

upperBound = mid;
if(upperBound == lowerBound && upperBound < 3){
break;
}
}
}
}
}

std::cout << "--------" << std::endl;
for (int p = 0; p <= lisPack.lisLength; p++){
std::cout << lisPack.lis[p][0];
std::cout << " [";
for (lisIndex = 1; lisIndex <= p+1; lisIndex++){
if (lisIndex == p+1){
std::cout << lisPack.lis[p][lisIndex];
} else {
std::cout << lisPack.lis[p][lisIndex] << ", ";
}
}
std::cout << "]" << std::endl;
}
lisPack.length = lisPack.lisLength + 1;
return lisPack;
}

int main() {
std::vector<int> sequence = {10, 22, 9, 33, 21, 50, 41, 60, 80};
longestIncreasingSubesequencePacked result = longestIncreasingSubsequence(sequence);
std::cout << "Length of the longest increasing subsequence: " << result.length << std::endl;

sequence = {6, 20, 1, 10, 9, 15, 7, 18, 11, 13, 100};
result = longestIncreasingSubsequenceContd(sequence, result);
std::cout << "Length of the longest increasing subsequence: " << result.length << std::endl;

sequence = {1, 2, 3, 4, 5, 104, 6};
result = longestIncreasingSubsequenceContd(sequence, result);
std::cout << "Length of the longest increasing subsequence: " << result.length << std::endl;

sequence = { 6, 20, 1, 10, 9, 15, 7, 18, 11, 13};
result = longestIncreasingSubsequence(sequence);
std::cout << "Length of the longest increasing subsequence: " << result.length << std::endl;

sequence = {5, 17, 4, 9, 13, 11, 15, 14, 8, 18};
result = longestIncreasingSubsequence(sequence);
std::cout << "Length of the longest increasing subsequence: " << result.length << std::endl;

sequence = {12, 6, 2, 20, 17, 11, 16, 15, 19, 3};
result = longestIncreasingSubsequence(sequence);
std::cout << "Length of the longest increasing subsequence: " << result.length << std::endl;

return 0;
}

Results in

------

9 [9]

21 [9, 21]

33 [10, 22, 33]

41 [10, 22, 33, 41]

60 [10, 22, 33, 41, 60]

80 [10, 22, 33, 41, 60, 80]

Length of the longest increasing subsequence: 6

--------

1 [1]

7 [1, 7]

11 [1, 7, 11]

13 [1, 7, 11, 13]

60 [10, 22, 33, 41, 60]

80 [10, 22, 33, 41, 60, 80]

100 [10, 22, 33, 41, 60, 80, 100]

Length of the longest increasing subsequence: 7

--------

1 [1]

2 [1, 2]

3 [1, 2, 3]

4 [1, 2, 3, 4]

5 [1, 2, 3, 4, 5]

6 [1, 2, 3, 4, 5, 6]

100 [10, 22, 33, 41, 60, 80, 100]

104 [10, 22, 33, 41, 60, 80, 100, 104]

Length of the longest increasing subsequence: 8

--------

1 [1]

7 [1, 7]

11 [1, 7, 11]

13 [1, 7, 11, 13]

Length of the longest increasing subsequence: 4

--------

4 [4]

8 [4, 8]

11 [4, 9, 11]

14 [4, 9, 11, 14]

18 [4, 9, 11, 14, 18]

Length of the longest increasing subsequence: 5

--------

2 [2]

3 [2, 3]

15 [2, 11, 15]

19 [2, 11, 15, 19]

Le

ngth of the longest increasing subsequence: 4

## Create an account

Register a new account