write a program to find the nonempty, contiguous subarray of an Array whose values have the largest sum.This contiguous subarray is called the maximum subarray.
/*
* Brute Force
*/
int * FindMaxSubArray0(int A[], int n)
{
int i,j,sum,high,low;
int *max = (int *)malloc(n*sizeof(int));
int *end_pos = (int *)malloc(n*sizeof(int));
int *p = (int *) malloc(3* sizeof(int));
for(i = 0; i < n; i++) {
max[i] = A[i];
end_pos[i] = i;
sum = max[i];
for(j = i+1; j < n; j++) {
sum = sum + A[j];
if(sum > max[i]) {
max[i] = sum;
end_pos[i] = j;
}
}
}
p[0] = 0;
p[1] = end_pos[0];
p[2] = max[0];
for(i = 1; i < n; i++) {
if(max[i] > p[2]) {
p[2] = max[i];
p[0] = i;
p[1] = end_pos[i];
}
}
return p;
}
/*
* Divide-and-Conquer strategy
*/
int * FindMaxCrossSubArray(int A[],int low,int high,int mid)
{
int i,sumleft = A[mid],sumright = A[mid+1], sum,left,right;
int *p =(int *)malloc(sizeof(int) * 3);
sum = sumleft;
left = mid;
for(i = mid-1; i > low; i--) {
sum = sum+ A[i];
if(sum > sumleft) {
sumleft = sum;
left = i;
}
}
sum=sumright;
right = mid+1;
for(i = mid+2; i < high; i++) {
sum = sum + A[i];
if(sum > sumright) {
sumright = sum;
right = i;
}
}
p[0] = left;
p[1] = right;
p[2] = sumleft+sumright;
return p;
}
int * FindMaxSubArray1(int A[], int low, int high)
{
int mid, *left=NULL, *right=NULL, *cross=NULL, *p = NULL;
if(low == high) {
p =(int *)malloc(sizeof(int) * 3);
p[0] = p[1] = low;
p[2] = A[low];
return p;
} else {
mid = (low+high)/2;
left = FindMaxSubArray1(A,low,mid);
right = FindMaxSubArray1(A,mid+1,high);
cross = FindMaxCrossSubArray(A,low,high,mid);
if(left[2] >= right[2] && left[2] >= cross[2]) {
return left;
} else if(right[2] >= left[2] && right[2] >= cross[2]) {
return right;
} else {
return cross;
}
}
}
/*
* Dynamic Programmming Methodology
*/
int * FindMaxSubArray2(int A[], int n)
{
int *max, *end_pos, sum=0,*p,i;
max = (int*) malloc(sizeof(int)*n);
end_pos = (int*) malloc(sizeof(int)*n);
p = (int*) malloc(sizeof(int)*3);
for(i = 0; i < n; i++) {
max[i] = A[i];
end_pos[i] = i;
}
for(i = 1; i < n; i++) {
sum = max[i-1] + max[i];
if(sum > max[i]) {
max[i] = sum;
end_pos[i] = i;
}
}
p[2] = max[0];
for(i = 1; i < n; i++) {
if(max[i] > p[2]) {
p[2] = max[i];
p[1] = i;
}
}
for(i = p[1]; i > 0; i--) {
if(end_pos[i] == i) {
p[0] = i;
break;
}
}
}
/*
* Brute Force
*/
int * FindMaxSubArray0(int A[], int n)
{
int i,j,sum,high,low;
int *max = (int *)malloc(n*sizeof(int));
int *end_pos = (int *)malloc(n*sizeof(int));
int *p = (int *) malloc(3* sizeof(int));
for(i = 0; i < n; i++) {
max[i] = A[i];
end_pos[i] = i;
sum = max[i];
for(j = i+1; j < n; j++) {
sum = sum + A[j];
if(sum > max[i]) {
max[i] = sum;
end_pos[i] = j;
}
}
}
p[0] = 0;
p[1] = end_pos[0];
p[2] = max[0];
for(i = 1; i < n; i++) {
if(max[i] > p[2]) {
p[2] = max[i];
p[0] = i;
p[1] = end_pos[i];
}
}
return p;
}
/*
* Divide-and-Conquer strategy
*/
int * FindMaxCrossSubArray(int A[],int low,int high,int mid)
{
int i,sumleft = A[mid],sumright = A[mid+1], sum,left,right;
int *p =(int *)malloc(sizeof(int) * 3);
sum = sumleft;
left = mid;
for(i = mid-1; i > low; i--) {
sum = sum+ A[i];
if(sum > sumleft) {
sumleft = sum;
left = i;
}
}
sum=sumright;
right = mid+1;
for(i = mid+2; i < high; i++) {
sum = sum + A[i];
if(sum > sumright) {
sumright = sum;
right = i;
}
}
p[0] = left;
p[1] = right;
p[2] = sumleft+sumright;
return p;
}
int * FindMaxSubArray1(int A[], int low, int high)
{
int mid, *left=NULL, *right=NULL, *cross=NULL, *p = NULL;
if(low == high) {
p =(int *)malloc(sizeof(int) * 3);
p[0] = p[1] = low;
p[2] = A[low];
return p;
} else {
mid = (low+high)/2;
left = FindMaxSubArray1(A,low,mid);
right = FindMaxSubArray1(A,mid+1,high);
cross = FindMaxCrossSubArray(A,low,high,mid);
if(left[2] >= right[2] && left[2] >= cross[2]) {
return left;
} else if(right[2] >= left[2] && right[2] >= cross[2]) {
return right;
} else {
return cross;
}
}
}
/*
* Dynamic Programmming Methodology
*/
int * FindMaxSubArray2(int A[], int n)
{
int *max, *end_pos, sum=0,*p,i;
max = (int*) malloc(sizeof(int)*n);
end_pos = (int*) malloc(sizeof(int)*n);
p = (int*) malloc(sizeof(int)*3);
for(i = 0; i < n; i++) {
max[i] = A[i];
end_pos[i] = i;
}
for(i = 1; i < n; i++) {
sum = max[i-1] + max[i];
if(sum > max[i]) {
max[i] = sum;
end_pos[i] = i;
}
}
p[2] = max[0];
for(i = 1; i < n; i++) {
if(max[i] > p[2]) {
p[2] = max[i];
p[1] = i;
}
}
for(i = p[1]; i > 0; i--) {
if(end_pos[i] == i) {
p[0] = i;
break;
}
}
}