# 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].

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)

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)

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

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