Data Structure Questions and Answers – Maximum Sum of Continuous Subarray – 1

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Maximum Sum of Continuous Subarray – 1”.

1. 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?
a) Dynamic programming
b) Two for loops (naive method)
c) Divide and conquer
d) Dynamic programming, naïve method and Divide and conquer methods

Explanation: Dynamic programming, naïve method and Divide and conquer methods can be used to solve the maximum sub array sum problem.

2. Find the maximum sub-array sum for the given elements.
{2, -1, 3, -4, 1, -2, -1, 5, -4}
a) 3
b) 5
c) 8
d) 6

Explanation: The maximum sub-array sum is 5.

3. Find the maximum sub-array sum for the given elements.
{-2, -1, -3, -4, -1, -2, -1, -5, -4}
a) -3
b) 5
c) 3
d) -1

Explanation: All the elements are negative. So, the maximum sub-array sum will be equal to the largest element. The largest element is -1 and therefore, the maximum sub-array sum is -1.

4. Consider the following naive method to find the maximum sub-array sum:

```#include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
int cur_max, tmp_max, strt_idx, sub_arr_idx;
cur_max = arr[0];
for(strt_idx = 0; strt_idx < len; strt_idx++)
{
tmp_max=0;
for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
{
tmp_max +=arr[sub_arr_idx];
if(tmp_max > cur_max)
_____________;
}
}
printf("%d",cur_max);
return 0;
}```

Which line should be inserted to complete the above code?
a) tmp_max = cur_max
b) break
c) continue
d) cur_max = tmp_max

Explanation: If the tmp_max element is greater than the cur_max element, we make cur_max equal to tmp_max, i.e. cur_max = tmp_max.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

5. What is the time complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements?

```#include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
int cur_max, tmp_max, strt_idx, sub_arr_idx;
cur_max = arr[0];
for(strt_idx = 0; strt_idx < len; strt_idx++)
{
tmp_max=0;
for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
{
tmp_max +=arr[sub_arr_idx];
if(tmp_max > cur_max)
_____________;
}
}
printf("%d",cur_max);
return 0;
}```

a) O(n2)
b) O(n)
c) O(n3)
d) O(1)

Explanation: The naive method uses two for loops. The outer loop runs from 0 to n,
i.e. i = 0 : n.
The inner loop runs from i to n, i.e. j = i : n.
Therefore, the inner loop runs:
n times when the outer loop runs the first time.
(n-1) times when the outer loop runs the second time.
:
:
:
2 times when the outer loop runs (n-1)th time.
1 time when the outer loop runs nth time.
Therefore, time complexity = n + (n-1) + (n-2) + …… + 2 + 1 = n * (n + 1) /2 = O(n2).

6. What is the space complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements?

```#include<stdio.h>
int main()
{
int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9;
int cur_max, tmp_max, strt_idx, sub_arr_idx;
cur_max = arr[0];
for(strt_idx = 0; strt_idx < len; strt_idx++)
{
tmp_max=0;
for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
{
tmp_max +=arr[sub_arr_idx];
if(tmp_max > cur_max)
_____________;
}
}
printf("%d",cur_max);
return 0;
}```

a) O(n2)
b) O(1)
c) O(n3)
d) O(n)

Explanation: The naive method uses only a constant space. So, the space complexity is O(1).

7. What is the output of the following naive method used to find the maximum sub-array sum?

```#include<stdio.h>
int main()
{
int arr[1000] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9;
int cur_max, tmp_max, strt_idx, sub_arr_idx;
cur_max = arr[0];
for(strt_idx = 0; strt_idx < len; strt_idx++)
{
tmp_max = 0;
for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++)
{
tmp_max += arr[sub_arr_idx];
if(tmp_max > cur_max)
cur_max = tmp_max;
}
}
printf("%d",cur_max);
return 0;
}```

a) 6
b) 9
c) 7
d) 4

Explanation: The naive method prints the maximum sub-array sum, which is 7.

8. What is the time complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
a) O(n)
b) O(logn)
c) O(nlogn)
d) O(n2)

Explanation: The time complexity of the divide and conquer algorithm used to find the maximum sub-array sum is O(nlogn).

9. What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?
a) O(n)
b) O(1)
c) O(n!)
d) O(n2)

Explanation: The divide and conquer algorithm uses a constant space. So, the space complexity is O(1).

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]