Please write a Java program for the algorithm Comments will

Please write a Java program for the algorithm. Comments will be appreciated

(10 points) Design algorithm for maximum sum problem. Chapter 3, Exercise 38, page 150. For example, given the sequence 3, -5, 4,-3, 10, the output is 11 (4-3+10). Analyze the time complexity of the algorithm

Solution

// Find the maximum possible sum in arr[] auch that arr[m] is part of it

int maxCrossingSum(int arr[], int l, int m, int h)

{

    // Include elements on left of mid.

    int sum = 0;

    int left_sum = INT_MIN;

    for (int i = m; i >= l; i--)

    {

        sum = sum + arr[i];

        if (sum > left_sum)

          left_sum = sum;

    }

    // Include elements on right of mid

    sum = 0;

    int right_sum = INT_MIN;

    for (int i = m+1; i <= h; i++)

    {

        sum = sum + arr[i];

        if (sum > right_sum)

          right_sum = sum;

    }

    // Return sum of elements on left and right of mid

    return left_sum + right_sum;

}

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).

The Kadane’s Algorithm for this problem takes O(n) time. Therefore the Kadane’s algorithm is better than the Divide and Conquer approach, but this problem can be considered as a good example to show power of Divide and Conquer. The above simple approach where we divide the array in two halves, reduces the time complexity from O(n^2) to O(nLogn).