Answer to Question #191224 in C for CHANDAN MIshra

Question

Maximum Subarray Sum (Divide and Conquer)

Description

You are given an array containing 'n' elements. The array can contain both positive and negative integers. Determine the sum of the contiguous subarray with the maximum sum.

 

Consider the array {8, -9, 3, 6, 8, -5, 7, -6, 1, -3}.

The maximum subarray will be 3, 6, 8, -5, 7.

The maximum subarray sum will be 3+6+8+(-5)+7 = 19

 

Input Format:

The input contains the number of elements in the array, followed by the elements in the array.

 

Output Format:

The output contains the maximum subarray sum.

 

Sample Test Cases:

Input:

10 8 -9 3 6 8 -5 7 -6 1 -3

Output:

19 

 

Input:

5 8 9 4 5 7

 

Output:

33

Answer 1

#include<stdio.h>
#include<string.h>
#include<ctype.h>


int maxSubArraySum(int elements[],int n);


int main(){
	int elements[1000];
	int n=10;
	int i=0;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d",&elements[i]);
	}
	int maxSubSum= maxSubArraySum(elements,n);
	printf("%d\n\n",maxSubSum);
	getchar();
	getchar();
	return 0;
}


//use the Kadane Algorithm
int maxSubArraySum(int elements[],int n) {


	int maxElement = 0;
	int maxEndingElement = 0;
	for (int i = 0; i < n; i++) {
		maxEndingElement += elements[i];
		if (maxEndingElement < 0){
			maxEndingElement = 0;
		}else if (maxElement < maxEndingElement){
			maxElement = maxEndingElement;
		}
	}
	return maxElement;
}

Examples: