求最大子序列和

#include<stdio.h>
#include<stdlib.h>
#include"random_n.h"

#define MAX_NUM 100
/*
*Function:the most powerful method to solve the problem
*
*Huge:T = O(N)
*
*Author:Qinzhiguo
*
*Date:2012-1-30
*/

int MaxSubSum_HighSpeed(int a[],int N)
{
int ThisSum,MaxSum,i,j;

ThisSum=MaxSum=0;
for(i=0;i<N;i++)
{

ThisSum += a[i];
if(ThisSum > MaxSum)
{
MaxSum=ThisSum;
}
else if(ThisSum <0)
{
ThisSum=0;
}

}

return MaxSum;
}

/*
*Function: Max3 is a method to get the biggest one of 3 input numbers
*
*Author:Qinzhiguo
*
*Date:2012-2-3
*
*/
int Max3(int a,int b,int c)
{
if(a>=b && a>=c)
{
return a;
}
else if(b>=a && b>=c)
{
return b;
}
else if(c>=a && c>=b)
{
return c;
}
else
{
return -1;
}
}

/*
*Function:a recursive method to get the sub maxmimu sum of the sequence
*
*Author:Qinzhiguo
*
*Date:2012-2-3
*/

int MaxSubQuenceSum(int a[],int left,int right)
{
int MaxLeftSum,MaxRightSum;
int MaxLeftBorderSum,MaxRightBorderSum;
int LeftBorderSum,RightBorderSum;
int center,i;

if(left == right)
{
if(a[left] >0)
{
return a[left];
}
else
{
return 0;
}

}

center = (left + right) / 2;

MaxLeftSum=MaxSubQuenceSum(a,left,center);
MaxRightSum=MaxSubQuenceSum(a,center+1,right);

MaxLeftBorderSum=0;
LeftBorderSum=0;
for(i=center;i>=left;i--)
{
LeftBorderSum += a[i];
if(LeftBorderSum > MaxLeftBorderSum)
{
MaxLeftBorderSum=LeftBorderSum;
}
}

MaxRightBorderSum=0;
RightBorderSum=0;
for(i=center+1;i<=right;i++)
{
RightBorderSum +=a[i];
if(RightBorderSum > MaxRightBorderSum)
{
MaxRightBorderSum=RightBorderSum;
}
}

return Max3(MaxLeftSum,MaxRightSum,MaxLeftBorderSum+MaxRightBorderSum);

}

/*
*Function:get the maxsubsum by giving the argments input.
*
*Author:Qinzhiguo
*
*Date:2012-2-3
*/
int MaxSubSum(int a[],int n)
{
return MaxSubQuenceSum(a,0,n-1);
}

/*
*Function:Main indoor of the whole project
*
*Author:Qinzhiguo
*
*Date:2012-1-31
*/
int main()
{
int a[MAX_NUM];
int i=0,MaxSum=0;
while(i<MAX_NUM)
{
a[i]=0;
i++;
}
random_n(a,MAX_NUM);
MaxSum = MaxSubSum(a,MAX_NUM);

i=0;
while(i<MAX_NUM)
{
printf("%d ",a[i]);
i++;
}
printf("\nThe List MaxSubQueneSum is %d\n",MaxSum);

if(i==0)
{
printf("\nNothing is done!\n");
}
else
{
printf("\n------------Program Finshed------------\n");
}
return 0;

}

頭文件包含的random.h是我自己寫的一個產生隨機數的函數，大家可以自己實現，或者參考我之前博客中給出的生成隨機數的方法。

這樣在測試的時候具有比較大的優勢，減去了大數據量的輸入負擔。