Experiment- 1
Aim:
Given an array of integers (which may include negative numbers), find the maximum sum of a
contiguous sub array using the Divide and Conquer approach.
Description:
Divide and Conquer Strategy
The idea is to divide the array into two halves and find the maximum subarray sum in three
possible cases:
1. Entirely in the left half
2. Entirely in the right half
3. Crossing the middle element
The answer is the maximum of these three values.
Steps
1. Divide the array into two halves.
2. Recursively find the maximum subarray sum in the left half.
3. Recursively find the maximum subarray sum in the right half.
4. Find the maximum subarray sum that crosses the midpoint.
5. Return the maximum among the three sums.
Recurrence Relation
T(n)=2T(n2)+O(n)
Using the Master Theorem:
Time Complexity: O(n log n)
Space Complexity: O(log n)
Algorithm
1. Find the middle index.
2. Recursively find:
o Maximum subarray sum in the left half.
o Maximum subarray sum in the right half.
3. Find the maximum subarray sum that crosses the middle.
4. Return the maximum among the above three sums.
Program:
public class MaximumSubarrayDivideConquer {
// Function to find maximum crossing sum
static int maxCrossingSum(int arr[], int left, int mid, int right) {
int sum = 0;
int leftSum = Integer.MIN_VALUE;
// Find maximum sum on left side of mid
for (int i = mid; i >= left; i--) {
sum += arr[i];
if (sum > leftSum)
leftSum = sum;
}
sum = 0;
int rightSum = Integer.MIN_VALUE;
// Find maximum sum on right side of mid
for (int i = mid + 1; i <= right; i++) {
sum += arr[i];
if (sum > rightSum)
rightSum = sum;
}
return leftSum + rightSum;
}
// Divide and Conquer function
static int maxSubArraySum(int arr[], int left, int right) {
// Base case
if (left == right)
return arr[left];
int mid = (left + right) / 2;
int leftMax = maxSubArraySum(arr, left, mid);
int rightMax = maxSubArraySum(arr, mid + 1, right);
int crossMax = maxCrossingSum(arr, left, mid, right);
return [Link]([Link](leftMax, rightMax), crossMax);
}
public static void main(String[] args) {
int arr[] = {-2, -5, 6, -2, -3, 1, 5, -6};
int result = maxSubArraySum(arr, 0, [Link] - 1);
[Link]("Maximum Contiguous Subarray Sum = " + result);
}
}
OUTPUT:
Maximum Contiguous Subarray Sum = 7