Dynamic Programming In Data Structures - Study Mode
[#241] Consider the following code snippet. Which property is shown by line 4 of the below code snippet? 1. int sum[len], idx
2. sum[0] = arr[0]
3. for(idx = 1
idx < len
idx++)
4. sum[idx] = max(sum[idx - 1] + arr[idx], arr[idx])
5. int mx = sum[0]
6. for(idx = 0
idx < len
idx++)
7. if(sum[idx] > mx)
8. mx =sum[idx]
9. return mx
Correct Answer
(A) Optimal substructure
[#242] What is the output of the following implementation of Kadane's algorithm? #include<stdio.h>
int max_num(int a, int b)
{
if(a > b)
return a
return b
}
int kadane_algo(int *arr, int len)
{
int ans, sum, idx
ans =0
sum =0
for(idx =0
idx < len
idx++)
{
sum = max_num(0,sum + arr[idx])
ans = max_num(sum,ans)
}
return ans
}
int main()
{
int arr[] = {-2, -3, -3, -1, -2, -1, -5, -3},len = 8
int ans = kadane_algo(arr,len)
printf("%d",ans)
return 0
}
Correct Answer
(D) 0
[#243] What is the output of the following code? #include<stdio.h>
#include<limits.h>
int mat_chain_multiplication(int *mat, int n)
{
int arr[n][n]
int i,k,row,col,len
for(i=1
i<n
i++)
arr[i][i] = 0
for(len = 2
len < n
len++)
{
for(row = 1
row <= n - len + 1
row++)
{
col = row + len - 1
arr[row][col] = INT_MAX
for(k = row
k <= col - 1
k++)
{
int tmp = arr[row][k] + arr[k + 1][col] + mat[row - 1] * mat[k] * mat[col]
if(tmp < arr[row][col])
arr[row][col] = tmp
}
}
}
return arr[1][n - 1]
}
int main()
{
int mat[6] = {20,30,40,50}
int ans = mat_chain_multiplication(mat,4)
printf("%d",ans)
return 0
}
Correct Answer
(A) 64000
[#244] What is the output of the following code? #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[] = "abcd"
int ans = lps(str1)
printf("%d",ans)
return 0
}
Correct Answer
(B) 1
[#245] What is the time complexity of the following dynamic programming implementation used to find the length of the longest increasing subsequence? #include<stdio.h>
int longest_inc_sub(int *arr, int len)
{
int i, j, tmp_max
int LIS[len]
// array to store the lengths of the longest increasing subsequence
LIS[0]=1
for(i = 1
i < len
i++)
{
tmp_max = 0
for(j = 0
j < i
j++)
{
if(arr[j] < arr[i])
{
if(LIS[j] > tmp_max)
tmp_max = LIS[j]
}
}
LIS[i] = tmp_max + 1
}
int max = LIS[0]
for(i = 0
i < len
i++)
if(LIS[i] > max)
max = LIS[i]
return max
}
int main()
{
int arr[] = {10,22,9,33,21,50,41,60,80}, len = 9
int ans = longest_inc_sub(arr, len)
printf("%d",ans)
return 0
}
Correct Answer
(C) O(n 2 )