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 Posted January 1 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