数据结构学习笔记(2)--算法的威力II

继续来研究最大子序列和这个问题。

经过改良，逐层遍历这种方法的复杂度被从N3降到了N2的级别，可以说是一个非常大的进步了，还有没有更好的办法呢？

这时候该回顾下递归(Recursion)了，先举一个最简单的递归的例子，求一个整数的N次方：

大家都知道要求一个数的N次方的话，先得求出这个数的N-1次方… 以此类推，也就是从这个数的0次方开始，而下面的这段代码，正是用到了这种思想

下面这段代码只能处理幂是正整数的情况
public static int GetPow(int radix,int power)
{
if(power == 0)
{
return 1;
}
else
{
return radix * GetPow(radix, power - 1);
}
}

然后回到最大子序列上，其实仔细想一想，如果把这N个数从中间的那个数分开的话，那么具有最大子序列和的这个序列所在的位置，只有三种可能：左边、右边或者是中间。运用刚才的递归思想，不难编写出下面的Pseudocode：

Function Int PseudoGetMaxSubsequenceSum(Array array)
{
Array arrayLeft=Left(array);
Array arrayRight=Right(array);
Int leftMaxSum=PseudoGetMaxSubsequenceSum(arrayLeft);
Int rightMaxSum=PseudoGetMaxSubsequenceSum(arrayRight);
Int midMaxSum=GetMidMaxSum(array);
return MaxOfThree(leftMaxSum,rightMaxSum,midMaxSum);
}

然后逐步细化，将Left(),Right(),GetMidMaxSum()写成实际的方法，于是就有了下面的代码：

public static int RecursiveMaxSubsequenceSum(int[] arrNumbers, int left, int right)
{
if (left == right)
{
if (arrNumbers[left] > 0)
{
return arrNumbers[left];
}
else
{
return 0;
}
}
int center = (left + right) / 2;
//Calculate the max subsequence sum in the left part
int maxLeftSum = RecursiveMaxSubsequenceSum(arrNumbers, left, center);
//Calculate the max subsequence sum in the right part
int maxRightSum = RecursiveMaxSubsequenceSum(arrNumbers, center + 1, right);
//Equal to MidMaxSubsequenceSum
//Firstly, calculate the max subsequence sum from the center element of the array to the left edge
int maxLeftBorderSum = 0;
int leftBorderSum = 0;
for (int i = center; i >= left; i--)
{
leftBorderSum += arrNumbers[i];
if (leftBorderSum > maxLeftBorderSum)
{
maxLeftBorderSum = leftBorderSum;
}
}
//Secondly, calculate the max subsequence sum from the center element of the array to the right edge
int maxRightBorderSum = 0;
int rightBorderSum = 0;
for (int i = center + 1; i <= right; i++)
{
rightBorderSum += arrNumbers[i];
if (rightBorderSum > maxRightBorderSum)
{
maxRightBorderSum = rightBorderSum;
}
}

int maxMidSum = maxLeftBorderSum + maxRightBorderSum;

//Equal to MaxOfThree
return MaxOfThree(maxLeftSum, maxMidSum, maxRightSum);
}

public static int MaxOfThree(int a, int b, int c)
{
int temp;
if (a>b)
{
temp = a;
a = b;
b = temp;
}
if (a>c)
{
temp = a;
a = c;
c = temp;
}
if (b>c)
{
temp = b;
b = c;
c = temp;
}
return c;
}

根据书上的说法，采用递归的做法可将复杂度降低至N*logN的地步（这里就不给出具体的证明过程了）

接下来就是这个最令人拍案叫绝的算法了

public static int LinearMaxSubsequenceSum(int[] arrNumbers)
{
int maxSum = 0;
int tempSum = 0;
for (int i = 0; i <>
{
tempSum += arrNumbers[i];
if (tempSum>maxSum)
{
maxSum = tempSum;
}
else if (tempSum<0)
{
tempSum = 0;
}
}
return maxSum;
}

只用了一轮循环即完成运算，复杂度为N，原理请大家自己思考。