最大子数列问题问题描述

最大连续子数列和一道很经典的算法问题，给定一个数列，其中可能有正数也可能有负数，我们的任务是找出其中连续的一个子数列（不允许空序列），使它们的和尽可能大。我们一起用多种方式，逐步优化解决这个问题。

最大子数列问题暴力方法

求出所有可能连续子列的和，时间复杂度O(N^3)

intMaxSubSequm1(intA[],intN){intThisSum,MaxSum=0;inti,j,k;for(i=0;i
 
  MaxSum)
MaxSum=ThisSum;
}}
returnMaxSum;
}

 

最大子数列问题一个简单的优化

很显然上面的算法中，在计算子列和时，可以利用前一步计算和的结果，不需要每次从头累加。时间复杂度O(N^2) 。

intMaxSubSequm1(intA[],intN){
intThisSum,MaxSum=0;
inti,j,k;
for(i=0;i
 
  MaxSum)
MaxSum=ThisSum;
}
}
returnMaxSum;
}

 

最大子数列问题分而治之

1. 将问题一分为二，缩小问题规模，递归求解。

2. 此处求解过程中要从中间基准点开始，扫描求出跨界的最大连续子列和，然后和左右边的解比较求出最终的结果。

3. 时间复杂度O(N*logN)

最大子数列问题在线处理

我们可以通过抛弃负子列，保证最大子列和递增。当扫描一遍，最大子列和不再递增时，当前的最大子列和即为我们的解。这是最优算法，时间复杂度O(N)。

intMaxSubseqSum4(intA[],intN){
intThisSum,MaxSum;
inti;
ThisSum=MaxSum=0;
for(i=0;i
 
  MaxSum)
MaxSum=ThisSum;
elseif(ThisSum<0)
ThisSum=0;
}
returnMaxSum;
}