最大子序列和的接口函数（2）
int MaxSubsequenceSum(const int A[],int N){
int thisSum,MaxSum,i,j,k;
MaxSum=0;
for(i=1;i<N;i++)
{
for(j=i;j<N;j++)
{
thisSum=0;
for(k=i;k<j;j++)
{
thisSum+=A;
}
if(thisSum>MaxSum)
MaxSum=thisSum;
}
return MaxSum
}
}
举个例子，在test.c中：
#include <stdio.h>
#include <stdlib.h>
int MaxSubsequenceSum(const int A[],int N)
{
int thisSum,MaxSum,i,j,k;
MaxSum=0;
for(i=0;i<N;i++)
{
printf("i:%d ....\n",i);
for(j=i;j<N;j++)
{
printf("j:%d ....\n",j);
thisSum=0;
for(k=i;k<=j;k++)
{
printf("k:%d ....\n",k);
thisSum+=A;
}
if(thisSum>MaxSum)
MaxSum=thisSum;
}
}
return MaxSum;
}
int main()
{
int number[]={1,-1,3,4};
int maxsum=0;
printf("start ....\n");
maxsum=MaxSubsequenceSum(number,4);
printf("maxsum:%d\n",maxsum);
exit(0);
}
linux下编译运行
gcc -o sub maxsub.c
./sub
得出结果
start ....
i:0 ....
j:0 ....
k:0 ....
j:1 ....
k:0 ....
k:1 ....
j:2 ....
k:0 ....
k:1 ....
k:2 ....
j:3 ....
k:0 ....
k:1 ....
k:2 ....
k:3 ....
i:1 ....
j:1 ....
k:1 ....
j:2 ....
k:1 ....
k:2 ....
j:3 ....
k:1 ....
k:2 ....
k:3 ....
i:2 ....
j:2 ....
k:2 ....
j:3 ....
k:2 ....
k:3 ....
i:3 ....
j:3 ....
k:3 ....
maxsum:7
第一个for循环为N,第二个for循环大小为N-i;第三个for循环大小j-i+1;总数为O(1*N*N*N)=O()
https://blog.51cto.com/u_15459030/4811385
页:
[1]