Scribd
Upload
3 views2 pages

Maximum Subarray Lab

The document outlines an experiment to find the maximum sum of a contiguous subarray using the divide and conquer technique. It provides a detailed algorithm, C code implementation, and a sample input and output demonstrating the functionality. The time complexity is O(n log n) and the space complexity is O(log n).

Uploaded by

kingkunalsingh83
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views2 pages

Maximum Subarray Lab

The document outlines an experiment to find the maximum sum of a contiguous subarray using the divide and conquer technique. It provides a detailed algorithm, C code implementation, and a sample input and output demonstrating the functionality. The time complexity is O(n log n) and the space complexity is O(log n).

Uploaded by

kingkunalsingh83
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Experiment: Maximum Subarray (Divide and Conquer)

Aim
To find the maximum sum of a contiguous subarray using the divide and conquer technique.

Algorithm
1 Start the program.

2 Input the array elements.

3 Define function maxSubarray(low, high).

4 If low == high, return the element.

5 Find mid = (low + high)/2.

6 Recursively find maximum sum in left subarray.

7 Recursively find maximum sum in right subarray.

8 Find maximum crossing sum.

9 Traverse left from mid to find left sum.

10 Traverse right from mid to find right sum.

11 Return maximum of left, right and crossing sum.

12 Stop the program.

C Code
#include <stdio.h>
#include <limits.h>

int max(int a, int b) { return (a > b) ? a : b; }

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


int sum = 0, left_sum = INT_MIN;
for (int i = m; i >= l; i--) {
sum += arr[i];
if (sum > left_sum) left_sum = sum;
}

sum = 0;
int right_sum = INT_MIN;
for (int i = m + 1; i <= h; i++) {
sum += arr[i];
if (sum > right_sum) right_sum = sum;
}

return left_sum + right_sum;


}

int maxSubArray(int arr[], int l, int h) {


if (l == h) return arr[l];

int m = (l + h) / 2;

return max(maxSubArray(arr, l, m),


max(maxSubArray(arr, m+1, h),
maxCrossingSum(arr, l, m, h)));
}

int main() {
int arr[] = {2, -4, 3, -1, 2, 1, -5, 4};
int n = sizeof(arr)/sizeof(arr[0]);

printf("Maximum Subarray Sum = %d", maxSubArray(arr, 0, n-1));


return 0;
}

Sample Input
Array: 2 -4 3 -1 2 1 -5 4

Sample Output
Maximum Subarray Sum = 5

Complexity
Time Complexity: O(n log n)
Space Complexity: O(log n)

You might also like