WalidKhan Posted December 13, 2023 Posted December 13, 2023 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 Posted January 1, 2024 Posted January 1, 2024 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
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now