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?
Dynamic programming | |
Two for loops (naive method) | |
Divide and conquer | |
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}
3 | |
5 | |
8 | |
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}
-3 | |
5 | |
3 | |
-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?
tmp....max = cur....max | |
break | |
continue | |
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?
O(n2) | |
O(n) | |
O(n3) | |
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.