#include <bits/stdc++.h> using namespace std; // function that returns the length of the…
- User
#include <bits/stdc++.h> using namespace std;
// function that returns the length of the // longest increasing subsequence // whose adjacent element differ by 1 int longestSubsequence(int a[], int n) { // stores the index of elements unordered_map<int, int> mp;
// stores the length of the longest // subsequence that ends with a[i] int dp[n]; memset(dp, 0, sizeof(dp)); int maximum = INT_MIN; // iterate for all element for (int i = 0; i < n; i++) { // if a[i]-1 is present before i-th index if (mp.find(a[i] - 1) != mp.end()) { // last index of a[i]-1 int lastIndex = mp[a[i] - 1] - 1; // relation dp[i] = 1 + dp[lastIndex]; } else dp[i] = 1; // stores the index as 1-index as we need to // check for occurrence, hence 0-th index // will not be possible to check mp[a[i]] = i + 1; // stores the longest length maximum = max(maximum, dp[i]); } return maximum;}
// Driver Code int main() { int a[] = { 4, 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 }; int n = sizeof(a) / sizeof(a[0]); cout << longestSubsequence(a, n); return 0; }
CONCERT THIS CODE TO C LANGUAGE
- Assistant
Here's the same logic implemented in C. In C, we use
malloc()to allocate memory dynamically for thedparray, and we have to free that memory before exiting the program. We also have to usememsetandINT_MINfrom thelimits.hlibrary as well asstdlib.hfor themallocandfreefunctions.#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> // function that returns the length of the // longest increasing subsequence // whose adjacent element differ by 1 int longestSubsequence(int a[], int n) { // stores the index of elements int *mp = (int *)malloc((200001) * sizeof(int)); // Assuming the range of numbers is upto 200000 for (int i = 0; i < 200001; i++) { mp[i] = -1; // Initialize hash map with -1 } // stores the length of the longest // subsequence that ends with a[i] int *dp = (int *)malloc(n * sizeof(int)); memset(dp, 0, n * sizeof(int)); int maximum = INT_MIN; // iterate for all element for (int i = 0; i < n; i++) { // if a[i]-1 is present before i-th index if (mp[a[i] - 1] != -1) { // last index of a[i]-1 int lastIndex = mp[a[i] - 1] - 1; // relation dp[i] = 1 + dp[lastIndex]; } else dp[i] = 1; // stores the index as 1-index as we need to // check for occurrence, hence 0-th index // will not be possible to check mp[a[i]] = i + 1; // stores the longest length maximum = dp[i] > maximum ? dp[i] : maximum; } // Free the allocated memory free(mp); free(dp); return maximum; } // Driver Code int main() { int a[] = { 4, 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 }; int n = sizeof(a) / sizeof(a[0]); printf("%d", longestSubsequence(a, n)); return 0; }Please note that this implementation assumes the range of integers in the array
ais up to 200000 (adjust if necessary). The hashmapmpis now a large array initialized with-1, which is used to represent that a number has not yet been encountered. When we use a number as an index intomp, we're effectively using it as a key in the hashmap. - User
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> static int lastIndex = 0; int longestSubsequence(int a[], int n) { int *mp = (int *)malloc((200001) * sizeof(int)); for (int i = 0; i < 200001; i++) { mp[i] = -1; }
int *dp = (int *)malloc(n * sizeof(int)); memset(dp, 0, n * sizeof(int)); int maximum = INT_MIN; for (int i = 0; i < n; i++) { if (mp[a[i] - 1] != -1) { lastIndex = mp[a[i] - 1] - 1; dp[i] = 1 + dp[lastIndex]; } else dp[i] = 1; mp[a[i]] = i + 1; maximum = dp[i] > maximum ? dp[i] : maximum; } free(mp); free(dp); return maximum;}
int main() { int a[] = { 4, 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 }; int n = sizeof(a) / sizeof(a[0]); printf("%d", longestSubsequence(a, n)); printf("%d",)
return 0;}
same program but i also need to print the indexes of the longest subsequen
- Assistant
To print the indexes of the longest subsequence whose adjacent elements differ by 1 in addition to the length of the subsequence, you need to modify the
longestSubsequencefunction. Instead of only tracking the maximum length, you will also need to backtrack from the maximum length index to reconstruct the actual sequence.Below is the modified code that prints both the length and the indexes of the longest subsequence:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> int * reconstructSequence(int *dp, int *track, int index, int *size) { // Backtracking from last index to reconstruct the sequence int count = dp[index]; *size = count; // Set the size of the sequence int *sequence = (int *)malloc(count * sizeof(int)); if (!sequence) { perror("Memory allocation failed"); exit(EXIT_FAILURE); } int current = index; while (count > 0) { sequence[--count] = current; // Store the index current = track[current]; } return sequence; } int longestSubsequence(int a[], int n) { // Allocate memory for mapping and dp array int *mp = (int *)malloc((200001) * sizeof(int)); if (!mp) { perror("Memory allocation failed"); exit(EXIT_FAILURE); } for (int i = 0; i < 200001; i++) { mp[i] = -1; } int *dp = (int *)malloc(n * sizeof(int)); if (!dp) { perror("Memory allocation failed"); exit(EXIT_FAILURE); } memset(dp, 0, n * sizeof(int)); // Array to track previous index in the longest subsequence int *track = (int *)malloc(n * sizeof(int)); if (!track) { perror("Memory allocation failed"); exit(EXIT_FAILURE); } for (int i = 0; i < n; i++) { track[i] = -1; // Initialize to -1 } int maximum = INT_MIN; int maxIndex = 0; for (int i = 0; i < n; i++) { if (mp[a[i] - 1] != -1) { int prevIndex = mp[a[i] - 1] - 1; dp[i] = dp[prevIndex] + 1; track[i] = prevIndex; // Track the index } else { dp[i] = 1; } mp[a[i]] = i + 1; if (dp[i] > maximum) { maximum = dp[i]; maxIndex = i; } } // Reconstruct and print the longest subsequence int seqSize; int *sequence = reconstructSequence(dp, track, maxIndex, &seqSize); printf("Length of longest subsequence: %d\n", maximum); printf("Indexes of longest subsequence: "); for (int i = 0; i < seqSize; ++i) { printf("%d ", sequence[i]); } printf("\n"); // Free the allocated memory free(mp); free(dp); free(track); free(sequence); return maximum; } // Driver Code int main() { int a[] = { 4, 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 }; int n = sizeof(a) / sizeof(a[0]); longestSubsequence(a, n); return 0; }This code finds the longest increasing subsequence whose adjacent elements differ by 1 and also prints the indexes. The function
reconstructSequenceuses thetrackarray to walk back through the indices of the subsequence to provide the correct sequence order.