# Data Structure Questions and Answers-Maximum Sum of Continuous Subarray

## Click on any option to know the CORRECT ANSWERS

 Question 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 All of the mentioned

Question 1 Explanation:
All of the methods mentioned can be used to solve the maximum sub-array sum problem.

 Question 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

Question 2 Explanation:
The maximum sub-array sum is 5.

 Question 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

Question 3 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.

 Question 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

Question 4 Explanation:
If the tmp....max element is greater than the cur....max element, we make cur....max equal to tmp....ma, x i.e. cur....max = tmp....max.

 Question 5
What is the time complexity of the naive method used to find the maximum sub-array sum in an array containing n elements?
 A O(n2) B O(n) C O(n3) D O(1)

Question 5 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).

There are 5 questions to complete.