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
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
NTA NET Questions answers

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
Commerce Questions answers

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
Education Questions answers

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
Reasoning Questions answers

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)
GK Questions answers

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.

 

 Download all FREE PDF Ebook >>>CLICK HERE<<<