算法是为求解一个问题需要遵循的、被清楚地指定的简单的指令的集合。对于一个问题,一旦给定某种算法并且确定是正确的,那么重要的一步是确定该算法将需要多少诸如时间和空间的问题,也就是要分析该算法的时间复杂度和空间复杂度,时间复杂度低和空间复杂度低就代表该算法是好的,但我们要努力找到最优的算法。下面来看看最大子序列和问题的最优求解算法,用 php 实现了
- function maxSubSum($arr) {
- $maxSum = $sum = $leftIndex = $rightIndex = 0;
- $flag = false;
- foreach ($arr as $key=>$value) {
- $sum += $value;
- if ($sum > $maxSum) {
- $maxSum = $sum;
- if($flag) {
- $leftIndex = $key;
- $flag = false;
- }
- $rightIndex = $key;
- }
- if($sum <0) {
- $sum = 0;
- $flag = true;
- }
- }
- return array_slice($arr,$leftIndex,($rightIndex - $leftIndex)+1);
- }
再来看看 python 实现
- #!/usr/bin/python
- def findMaxSubArray( inputList ):
- if ( len( inputList ) == 0 ):
- return inputList
- middle = len( inputList ) / 2
- leftSum,rightSum,crossingSum,tmpSum = 0,0,0,0
- leftIndex,rightIndex = 0,len(inputList)
- leftSum = sum(inputList[0:middle])
- rightSum = sum(inputList[middle+1:])
- tmpIndex = middle -1
- while ( tmpIndex >0):
- tmpSum +=inputList[tmpIndex]
- if(tmpSum > leftSum):
- leftIndex = tmpIndex
- break;
- tmpIndex = tmpIndex - 1
- tmpIndex = middle+1
- while (tmpIndex < len( inputList )):
- tmpSum += inputList[tmpIndex]
- if( tmpSum > rightSum ):
- rightIndex = tmpIndex
- break;
- tmpIndex = tmpIndex + 1
- return inputList[leftIndex:rightIndex]
- if __name__ == '__main__':
- inputList = [-1,-2,-4,-8,-3,-10,-13,-56,-33,-2,-4,-45,-55,-12,-3]
- #inputList = [1,2,-4,8,4,0,-10,3,56,33,2,4,-45,55,0,-12,3]
- print findMaxSubArray ( inputList )
最后我想请教一个问题,为什么求余运算耗费很大,知道原理的请解答一下。
来源: http://www.bubuko.com/infodetail-2012934.html