lt;数据结构与算法分析gt;读书笔记--最大子序列和问题的求解
|
副标题[/!--empirenews.page--]
? 现在我们将要叙述四个算法来求解早先提出的最大子序列和问题。 第一个算法，它只是穷举式地尝试所有的可能。for循环中的循环变量反映了Java中数组从0开始而不是从1开始这样一个事实。还有，本算法并不计算实际的子序列；实际的计算还要添加一些额外的代码。 public static int maxSubSum1(int[] a) {
int maxSum = 0;
for(int i = 0;i<a.length;i++)
int j = i;j<a.length;j++) {
int thisSum = 0;
int k = i;k<=j;k++)
thisSum +=a[k];
if(thisSum > maxSum)
maxSum = thisSum;
}
return maxSum;
}
? 该算法肯定会正确运行(这用不着花太多时间去证明)。运行时间为O(N的3次方)，这完全取决这两行代码: )
thisSum +=a[k];
? 它们由一个含于三种嵌套for循环中的O(1）语句组成。 下面这行代码循环大小为N int i = 0;i<a.length;i++) ? 第二个循环大小为N-i，它可能要小，但也可能是N。我们必须假设最坏的情况，而这可能会使得最终的界有些大。第三个循环的大小为j-i+1我们也要假设它的大小为N。因此总数为 O(1.N.N.N)=O(N的3次方)。 而下面这行代码，开销只是O(1) int maxSum = 0; ? 然而，下面这段代码也只不过总共开销O(N的2次方)，因为它们只是两层循环内部的简单表达式 maxSum)
maxSum = thisSum;
? ? 第二个算法显然是O(N的2次方) int maxSubSum2( [] a) {
;
) {
;
for (int j = 0; j < a.length; j++) {
thisSum += a[j];
maxSum)
maxSum = thisSum;
}
}
maxSum;
}
? 对这个问题有一个递归和相对复杂的O(N logN)解法，我们现在就来描述它。要是真的没出现O(N)(线性的)解法，这个算法就会是体现递归威力的极好的范例。该方法采用一种对它们求解，这是“分”的部分。“治”阶段将两个子问题的解修补到一起并可能再做些少量的附加工作，最后得到整个问题的解。 在我们的例子中，最大子序列和可能在三处出现。或者整个出现在输入数据的左半部，或者整个出现在右半部，或者跨越输入数据的中部从而位于左右两半部分之中。前两种情况可以递归求解。第三种情况的最大和可以通过求出前半部分(包含前半部分最后一个元素)的最大和以及后半部分(包含后半部分第一个元素)的最大和而得到。此时将这两个和相加。作为一个例子，考虑下列输入，如图:
? 其中前半部分的最大子序列和为6(从元素A1到元素A3)而后半部分的最大子序列和为8(从元素A6到A7）。 前半部分包含其最后一个元素的最大和子序列和是4(从元素A1到元素A4）,而后半部分 包含其第一个元素的最大和是7(从元素A5到A7）。因此，横跨这部分且通过中间的最大和为4+7=11(从元素A1到A7）。 我们看到，在形成本例中的最大和子序列的三种方式中，最好的方式是包含两部分的元素。于是，答案为11。 ? 有必要对算法3的程序进行一些说明。递归过程调用的一般形式是传递输入的数组以及左边界和右边界，它们界定了数组要被处理的部分。单行驱动程序通过传递数组以及边界0和N-1而将该过程启动。 ? 代码示例如下: package cn.simple.example;
class AlgorithmTestExample {
maxSum;
}
maxSum;
}
private int maxSumRec(int [] a,int left,1)"> right) {
if(left == right)
if(a[left] > 0)
a[left];
else
return 0;
int center = (left + right)/2;
int maxLeftSum = maxSumRec(a,left,center);
int maxRightSum = maxSumRec(a,center+1,right);
int maxLeftBorderSum = 0,leftBorderSum = 0int i = center;i>=left;i--) {
leftBorderSum +=a[i];
if(leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}
int maxRightBorderSum = 0,rightBorderSum = 0int i = center+1;i<=right;i++) {
rightBorderSum += a[i];
if(rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}
return max3(maxLeftSum,maxRightSum,maxLeftBorderSum + maxRightBorderSum);
}
int max3(int maxLeftSum,1)">int maxRightSum,1)"> i) {
max;
if(maxLeftSum > maxRightSum)
max = maxLeftSum;
else
max = maxRightSum;
if(i > max)
max = i;
max;
}
int maxSubSum3(return maxSumRec(a,a.length-1);
}
}
? 看这段代码，如下所示: ;
? 如果left==right，那么只有一个元素，并且当该元素非负时它就是最大子序列。left>right的情况是不可能出现的，除非N是负数(不过，程序中小的扰动有可能致使这种混乱产生)。 ? 下面这两个递归调用，我们可以看到，递归调用总是对小于原问题的问题进行，不过程序小的扰动有可能破坏这个特性。
|
