81. What is the output of the following code?
#include<stdio.h>
#include<limits.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 max_sum_rectangle(int arr[][5],int row,int col)
{
int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
for(left = 0; left < col; left++)
{
for(right = left; right < col; right++)
{
if(right == left)
{
for(idx = 0; idx < row; idx++)
tmp[idx] = arr[idx][right];
}
else
{
for(idx = 0; idx < row; idx++)
tmp[idx] += arr[idx][right];
}
val = kadane_algo(tmp,row);
if(val > mx_sm)
mx_sm = val;
}
}
return mx_sm;
}
int main()
{
int arr[2][5] ={{1, 2, -1, -4, -20}, {-4, -1, 1, 7, -6}};
int row = 2, col = 5;
int ans = max_sum_rectangle(arr,row,col);
printf("%d",ans);
return 0;
}
#include<stdio.h>
#include<limits.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 max_sum_rectangle(int arr[][5],int row,int col)
{
int left, right, tmp[row], mx_sm = INT_MIN, idx, val;
for(left = 0; left < col; left++)
{
for(right = left; right < col; right++)
{
if(right == left)
{
for(idx = 0; idx < row; idx++)
tmp[idx] = arr[idx][right];
}
else
{
for(idx = 0; idx < row; idx++)
tmp[idx] += arr[idx][right];
}
val = kadane_algo(tmp,row);
if(val > mx_sm)
mx_sm = val;
}
}
return mx_sm;
}
int main()
{
int arr[2][5] ={{1, 2, -1, -4, -20}, {-4, -1, 1, 7, -6}};
int row = 2, col = 5;
int ans = max_sum_rectangle(arr,row,col);
printf("%d",ans);
return 0;
}82. What is the space complexity of the following dynamic programming implementation used to compute the nth fibonacci term?
int fibo(int n)
int fibo_terms[100000] //arr to store the fibonacci numbers
fibo_terms[0] = 0
fibo_terms[1] = 1
for i: 2 to n
fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
return fibo_terms[n]
int fibo(int n)
int fibo_terms[100000] //arr to store the fibonacci numbers
fibo_terms[0] = 0
fibo_terms[1] = 1
for i: 2 to n
fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2]
return fibo_terms[n]83. Longest palindromic subsequence is an example of . . . . . . . .
84. What is the output of the following code?
#include<stdio.h>
int balanced_partition(int *arr, int len)
{
int sm = 0, i, j;
for(i = 0;i < len; i++)
sm += arr[i];
if(sm % 2 != 0)
return 0;
int ans[sm/2 + 1][len + 1];
for(i = 0; i <= len; i++)
ans[0][i] = 1;
for(i = 1; i <= sm/2; i++)
ans[i][0] = 0;
for(i = 1; i <= sm/2; i++)
{
for(j = 1;j <= len; j++)
{
ans[i][j] = ans[i][j-1];
if(i >= arr[j - 1])
ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
}
}
return ans[sm/2][len];
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, len = 9;
int ans = balanced_partition(arr,len);
if(ans == 0)
printf("false");
else
printf("true");
return 0;
}
#include<stdio.h>
int balanced_partition(int *arr, int len)
{
int sm = 0, i, j;
for(i = 0;i < len; i++)
sm += arr[i];
if(sm % 2 != 0)
return 0;
int ans[sm/2 + 1][len + 1];
for(i = 0; i <= len; i++)
ans[0][i] = 1;
for(i = 1; i <= sm/2; i++)
ans[i][0] = 0;
for(i = 1; i <= sm/2; i++)
{
for(j = 1;j <= len; j++)
{
ans[i][j] = ans[i][j-1];
if(i >= arr[j - 1])
ans[i][j] = ans[i][j] || ans[i - arr[j - 1]][j - 1];
}
}
return ans[sm/2][len];
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}, len = 9;
int ans = balanced_partition(arr,len);
if(ans == 0)
printf("false");
else
printf("true");
return 0;
}85. In which of the following cases the minimum no of insertions to form palindrome is maximum?
86. Suppose you have coins of denominations 1, 3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm NOT produce an optimal answer?
87. Find the maximum sub-array sum for the following array:
{3, 6, 7, 9, 3, 8}
{3, 6, 7, 9, 3, 8}
88. You are given a boolean expression which consists of operators &, | and ∧ (AND, OR and XOR) and symbols T or F (true or false). You have to find the number of ways in which the symbols can be parenthesized so that the expression evaluates to true. This is the boolean parenthesization problem. Which of the following methods can be used to solve the problem?
89. If a problem can be broken into subproblems which are reused several times, the problem possesses . . . . . . . . property.
90. Given a one-dimensional array of integers, you have to find a sub-array with maximum sum. This is the maximum sub-array sum problem. Which of these methods can be used to solve the problem?
Read More Section(Dynamic Programming in Data Structures)
Each Section contains maximum 100 MCQs question on Dynamic Programming in Data Structures. To get more questions visit other sections.