If you are using divide and conquer to solve the problems, then your solution mu

Question

If you are using divide and conquer to solve the problems, then your solution must clearly and specify describe each of the following steps:

• Dividing the problem into sub problems

• Solving sub problems

• Merging solutions of sub problems.

Then, you must derive a recurrence relation for the run-time of the algorithm, and solve the recurrence relation. In this PA, you may assume that n is a power of 2 (if it helps).

Let A = [a1, a2, · · · , an] be an array of integers. Given 1 i < j n,

Give an algorithm to compute maxi,j Sij , analyze the run-time.

Explanation / Answer

Maximum sub array sum problem using divide and conquer method:

General steps of D&C for max sub array is-

1.Divide the given array in two parts.

2. Determine the max of following 3 cases:

A. Maximum subarray sum in left half [using recursive call].

            B. Maximum subarray sum in right half [using recursive call].

            C. Maximum subarray sum.

Pseudocode:

Base case: IF start =end return array[start];

** Here in this section we are dividing the problem into sub problems.

** in this section we are solving the problems and merging the sub problems and returning back.

Time complexity:

MaxSubArraySum() is recursive method and time complexity can be expressed in following recurrence relation.

T(n)= 2xT(n/2) + O(n);

Then from the case-2 of the master theorem it can be reduced to O(nlogn).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.