#include "stdio.h"
//算法1:
int MaxSubsequenceSum1(const int A[], int N)
{
int ThisSum, MaxSum, i, j, k;
MaxSum = 0;
for(i = 0; i < N; i++)
for(j = i; j < N; j++)
{
ThisSum = 0;
for(k = i; k <= j; k++)
ThisSum += A[k];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
return MaxSum;
}
//算法2:
int MaxSubsequenceSum2(const int A[], int N)
{
int ThisSum, MaxSum, i, j;
MaxSum = 0;
for(i = 0; i < N; i++)
{
ThisSum = 0;
for(j = i; j < N; j++)
{
ThisSum += A[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
//算法4:
int MaxSubsequenceSum4(const int A[], int N)
{
int ThisSum, MaxSum, i;
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;
}
//测试
int main()
{
int a[] = {-2, 11, -4, 13, -5, -2};
int size = sizeof(a) / sizeof(a[0]);
printf("MaxSubsequenceSum1 :%d\n", MaxSubsequenceSum1(a, size));
printf("MaxSubsequenceSum2 :%d\n", MaxSubsequenceSum2(a, size));
printf("MaxSubsequenceSum4 :%d\n", MaxSubsequenceSum4(a, size));
return 0;
}
