求子串和的最大值(最慢与最快)

我就是我 2022-11-28 10:43 188阅读 0赞

最慢的O(N*N*N)：

#include"stdio.h"
int MaxSubseqSum(int a[],int n)
{
    int ThisSum,MaxSum=0;
    int i,j,k;
    for(i=0;i<n;i++)
    {
        for(j=i;j<n;j++)
        {
            ThisSum=0;
            for(k=i;k<=j;k++)
            {
                ThisSum+=a[k];
                printf("%d  ",ThisSum);
            }
                    printf("--------\n");
            if(ThisSum>MaxSum)
             MaxSum=ThisSum;
        }
    }
return MaxSum;
}
int main()
{
    int b[]={1,2,-1,8,-3,5,9,-7};
    int data;
    data=MaxSubseqSum(b,8);
    printf("%d",data);
}

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZ3VvcWluZw_size_16_color_FFFFFF_t_70

最快的O(N)：

#include"stdio.h"
int MaxSubseqSum4(int a[],int n)
{
    int ThisSum,MaxSum;
    int i;
    ThisSum=MaxSum=0;
    for(i=0;i<n;i++)
    {
            ThisSum+=a[i];
            printf("%d  \n",ThisSum);              
            if(ThisSum>MaxSum)
                 MaxSum=ThisSum;
             else if(ThisSum<0)
                  ThisSum=0;
    }
     return MaxSum;
}
int main()
{
    int b[]={1,2,-1,8,-3,5,9,-7};
    int data;
    data=MaxSubseqSum4(b,8);
    printf("%d",data);
}