Register

GO Classes DPP | GATE CS, DA | Algorithms | Max Sum Subarray

161 views
2 2 votes

In the divide-and-conquer algorithm for maximum sum subarray, the maximum subarray may lie:

  1. entirely in the left half
     
  2. entirely in the right half

What is the third possible case?

  1. It must contain only positive elements.
     
  2. It must be exactly the middle element.
     
  3. It crosses the middle, using a suffix of the left half and a prefix of the right half.
     
  4. It must start at the first element and end at the last element.

1 Answer

0 0 votes

In divide and conquer for maximum sum subarray, the array is divided into two halves.

The maximum sum subarray can occur in three possible ways.

Case $1$: It lies completely in the left half.

Case $2$: It lies completely in the right half.

Case $3$: It crosses the middle.

If it crosses the middle, then it must include:

  • a suffix of the left half
     
  • a prefix of the right half

So, the crossing sum is calculated by taking the best suffix sum from the left side and the best prefix sum from the right side.

Therefore, the third possible case is:

It crosses the middle, using a suffix of the left half and a prefix of the right half.

Answer: C

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

3 3 votes
1 1 answer
187
187 views
GO Classes asked Aug 4
187 views
GO Classes DPP | GATE CS, DA | Algorithms | Merge Sort
Merge sort divides an array of size $n$ into two halves, recursively sorts both halves, and then merges the two sorted halves.Which recurrence correctly represents merge ...
4 4 votes
1 1 answer
182
182 views
GO Classes asked Aug 4
182 views
GO Classes DPP | GATE CS, DA | Algorithms | Divide & Conquer
Karatsuba multiplication multiplies two $n$-digit numbers by reducing the number of recursive half-size multiplications.Which recurrence represents Karatsuba multiplicati...
3 3 votes
1 1 answer
155
155 views
GO Classes asked Aug 4
155 views
GO Classes DPP | GATE CS, DA | Algorithms | Local Minimum
An array has distinct elements. A local minimum is an element smaller than both of its neighbors, with endpoints compared to their only neighbor.A divide-and-conquer algo...
3 3 votes
1 1 answer
186
186 views
GO Classes asked Aug 4
186 views
GO Classes DPP | GATE CS, DA | Algorithms | Divide & Conquer
Suppose array $A[1 \ldots n]$ is sorted in non-decreasing order and it is guaranteed that there exists an index $i$ such that:$A[i] = i$A divide-and-conquer algorithm che...