《最大子序列的分析》

算法一（O(n^3)）

int MaxSubseqSum1(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];
            if(ThisSum >MaxSum)
                MaxSum = ThisSum;
        }
    }
    return MaxSum;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

算法二(O(n^2))

int MaxSubseqSum2(int A[], int N)
{
    int i, j;
    int ThisSum, 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;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

算法三：（分治）

算法四：（在线处理）线性算法

int MaxSubseqSum4(int A[], int N)
{
    int i;
    int 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;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

文章来源: recclay.blog.csdn.net，作者：ReCclay，版权归原作者所有，如需转载，请联系作者。

原文链接：recclay.blog.csdn.net/article/details/77885442