Let A1n be an array containing n distinct real numbers some

Let A[1..n] be an array containing n distinct real numbers (some of these may be negative). (a) Design a O(n) time algorithm that computes an index j for which the sum A[1] + A[2] + · · · + A[j] is maximum. Write your algorithm in pseudocode. (b) Design a O(n log(n)) time algorithm that computes two indices i and j (where i j) for which the sum A[i] + A[i + 1] + · · · + A[j 1] + A[j] is maximum. Describe your algorithm in plain English. Moreover, you must use the Divideand-Conquer approach, write the recursion equation for the time of computation of your algorithm and solve it.

Solution

Hi, Please find my algorithm.

I have explained in very simple english

1)

Initialize:
max_so_far = 0
max_ending_here = 0

Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far

This is called Kadane’s Algorithm

Simple idea of the Kadane\'s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far
Time Complexity: O(n)

2)
1) Divide the given array in two halves
2) Return the maximum of following three
….a) Maximum subarray sum in left half (Make a recursive call)
….b) Maximum subarray sum in right half (Make a recursive call)
….c) Maximum subarray sum such that the subarray crosses the midpoint

The lines 2.a and 2.b are simple recursive calls. How to find maximum subarray sum such that the subarray crosses the midpoint? We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. Finally, combine the two and return.
Time Complexity: maxSubArraySum() is a recursive method and time complexity can be expressed as following recurrence relation.
T(n) = 2T(n/2) + (n)
The above recurrence is similar to Merge Sort and can be solved either using Recurrence Tree method or Master method. It falls in case II of Master Method and solution of the recurrence is (nLogn).