Jump to content

Dynamic Programming Challenge: Longest Increasing Subsequence

WalidKhan
in Computer Science

Featured Replies

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!

  • 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

 

 

Please sign in to comment

You will be able to leave a comment after signing in

Sign In Now
https://www.scienceforums.net/topic/133045-dynamic-programming-challenge-longest-increasing-subsequence/
Go to topic listing

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.