最大子序列和

时间:2022-07-30 19:24:20

一、遍历所有可能情况

(1234...N)所有可能子序列如下:

1;12;123......

2;23;234......

......

N

共N趟,没趟可能的情况由N,N-1...,1依次递减。

时间复杂度O(N3)的算法:

int MaxSubsequenceSum( const int A[ ] , int N)

{

int MaxSum = 0;

for(int i = 0; i < N; i++)  //控制趟数为N

//每趟可能的子序列和有以下两个循环控制。

  for(int j = i; j < N; j++)  //控制每趟的开始位置

  {

    int sum = 0;

    for(int k = j; k < N; k++)

    {

      sum += A[k];

      if(sum > MaxSum)

      MaxSum = sum;

    }

  }

  return MaxSum;

}

二、时间复杂度O(N2)

不考虑程序跑的趟数,直接罗列所有情况

int MaxSum = 0;

for(i = 0; i < N; i++)

{

  sum = 0;

  for(j = i; j < N; j++)

  {  

    sum += A[j];   

    if(MaxSum < sum)

    MaxSum = sum;

  }

return MaxSum;

}

三、相对复杂度O(N*logN)递归算法

分而治之:将问题分解为两个大小大致相等的子问题——分;两个子问题的解合并到一起并再做些少量附加工作,最后得到整个问题的解——治。

最大子序列可能出现的位置为数据的左半边,数据的右半边,数据的中部。

从概率论的角度来解读就是找出事件的完备事件组,将情况分为两类:1、包含中间元素;2、不含中间元素。其中不含中间元素又分左右侧两种情况。

int MaxSubsequenceSum( const int A[ ], int N)

{

  return MaxSubSum(A, 0, N-1);   //增加边界的参数

}

static int MaxSubSum( const int A[ ], left, right)

{

  if(left == right)

    if(A[left] > 0)

    return A[left];

    else return 0;

  int center = (left + right)/2;

  int MaxLeftSum = MaxSubSum(A, left, center);

  int MaxRightSum = MaxSubSum(A, left, center);

int maxLeftSum = 0;  

for(int i = center; i >= left; i--)

  {

    int leftSum += A[i];

      if(maxLeftSum < leftSum)

    maxLeftSum = leftSum;

  }

int maxRight = 0;

  for(int j = center; j <=right; j--)

  {

    int rigthSum += A[j];

    if(maxRightSum < rightSum )

    maxRightSum = rightSum;

  }

return Max3(MaxLeftSum, MaxRightSum, maxRightSum+maxLeftSum);

}

int Max3(a,b,c)

{

  return a > (b>c?b:c)?a:(b>c?b:c);

}

四、时间复杂度O(N)

1、如果sum<0,将sum置0,maxSum不更新,即maxSum从序列中首正数开始记录;

2、将求和的几个元素看做一个单元组,包含首正数的单元组中出现大于首正数时,更新maxSum,即maxSum=sum,此时maxSum存放当前最大子序列和;

3、当有负数出现时,sum<maxSum,maxSum不更新。当sum<0时,该单元组整体为一个负数,其后每个单元组包含该单元组都是负增长,故将sum置0,maxSum不更新;

int MaxSubsequenceSum( const int A[], int N)

{

  int sum = 0; int maxSum = 0;

  for(int i = 0 ; i < N; i++)

  {

    sum += A[i];

    if(maxSum < sum)

     maxSum = sum;

    else if(sum < 0)

      sum = 0;

  }

return maxSum;

}