What Is The Space Complexity Of The Following Dynamic #2089

What is the space complexity of the following dynamic programming implementation to find the longest palindromic subsequence where the length of the string is n?</p> <pre><code class="language-c"> #include<stdio.h> #include<string.h> int max_num(int a, int b) { if(a > b) return a; return b; } int lps(char *str1) { int i,j,len; len = strlen(str1); char str2[len + 1]; strcpy(str2, str1); strrev(str2); int arr[len + 1][len + 1]; for(i = 0; i <= len; i++) arr[i][0] = 0; for(i = 0; i <= len; i++) arr[0][i] = 0; for(i = 1; i <= len; i++) { for(j = 1; j <= len; j++) { if(str1[i-1] == str2[j - 1]) arr[i][j] = 1 + arr[i - 1][j - 1]; else arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]); } } return arr[len][len]; } int main() { char str1[] = "ababcdabba"; int ans = lps(str1); printf("%d",ans); return 0; }</code></pre>

This multiple choice question (MCQ) is related to the book/course gs gs122 Data Communication and Computer Network. It can also be found in gs gs122 Dynamic Programming - Longest Palindromic Subsequence - Quiz No.1.

 #include<stdio.h> #include<string.h> int max_num(int a, int b) { if(a > b) return a; return b; } int lps(char *str1) { int i,j,len; len = strlen(str1); char str2[len + 1]; strcpy(str2, str1); strrev(str2); int arr[len + 1][len + 1]; for(i = 0; i <= len; i++) arr[i][0] = 0; for(i = 0; i <= len; i++) arr[0][i] = 0; for(i = 1; i <= len; i++) { for(j = 1; j <= len; j++) { if(str1[i-1] == str2[j - 1]) arr[i][j] = 1 + arr[i - 1][j - 1]; else arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]); } } return arr[len][len]; } int main() { char str1[] = "ababcdabba"; int ans = lps(str1); printf("%d",ans); return 0; }