Dynamic Programming Challenge: Longest Increasing Subsequence

[WalidKhan]

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!

[fiveworlds]

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