Data Structure Questions and Answers-Maximum Sum of Continuous Subarray

 

 Help authour, Buy PDF Ebook   >>>Click Here<<<

Data Structure Questions and Answers-Maximum Sum of Continuous Subarray

Click on any option to know the CORRECT ANSWERS

Question 1
Which line should be inserted in the blank to complete the following dynamic programming implementation of the maximum sub-array sum problem?

#include<stdio.h> int max....num(int a, int b) { if(a> b) 	 return a; return b; } int maximum....subarray....sum(int *arr, int len) { int sum[len], idx; sum[0] = arr[0]; for(idx = 1; idx < len; idx++) 	 sum[idx] = .....; int mx = sum[0]; for(idx = 0; idx < len; idx++) 	 if(sum[idx] > mx) 	 mx =sum[idx]; 	 return mx; } int main() { int arr[] = {-2, -5, 6, -2, 3, -1, 0, -5, 6}, len = 9; int ans = maximum....subarray....sum(arr, len); printf("%d", ans); return 0; }
A
max....num(sum[idx - 1] + arr[idx], arr[idx])
B
sum[idx - 1] + arr[idx].
C
min....num(sum[idx - 1] + arr[idx], arr[idx])
D
arr[idx].
KBC Questions answers

Question 1 Explanation: 
The array "sum" is used to store the maximum sub-array sum. The appropriate way to do this is by using:

sum[idx] = max....num(sum[idx - 1] + arr[idx], arr[idx]).

Question 2
What is the time complexity of the ABOVE dynamic programming algorithm used to find the maximum sub-array sum?
A
O(n)
B
O(logn)
C
O(nlogn)
D
O(n2)
Home science Questions answers

Question 2 Explanation: 
The time complexity of the above dynamic programming algorithm used to solve maximum sub-array sum is O(n).

Question 3
What is the space complexity of the ABOVE dynamic programming algorithm used to find the maximum sub-array sum?
A
O(n)
B
O(1)
C
O(n!)
D
O(n2)
Biology Questions answers

Question 3 Explanation: 
The above dynamic programming algorithm uses space equal to the length of the array to store the sum values. So, the space complexity is O(n).

Question 4
Consider the following 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;

Which property is shown by line 4 of the above code snippet?

A
Optimal substructure
B
Overlapping subproblems
C
Both overlapping subproblems and optimal substructure
D
None of the mentioned
Management Questions answers

Question 4 Explanation: 
The current sum (i.e. sum[idx]) uses the previous sum (i.e. sum[idx - 1]) to get an optimal value. So, line 4 shows the optimal substructure property.

Question 5
Consider the following 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;

Which method is used by line 4 of the above code snippet?

A
Divide and conquer
B
Recursion
C
Both memoization and divide and conquer
D
Memoization
Reading comprehension Questions answers

Question 5 Explanation: 
The array "sum" is used to store the previously calculated values, so that they aren't recalculated. So, line 4 uses the memoization technique.