已知整数数列an,求最大的连续的k项和（最长子序列），并输出连续项首项和末项的下标，分别用O(N^2),O(NlogN)，O（N）实现，然后产生大小为10^4 - 10^8的随机整数数组测试效率。现在O(N^2),O(NlogN)，O(N)的求最长子序列算法已经搞定，只有在O(NlogN)算法中，计算下标出了问题。
使用2分法递归求最长子序列。最长子序列可能在数列左侧，右侧，或者是横跨左右的部分。
当连续项在数列左侧，右侧无法确定首项和末项的下标。因为递归回溯的时候下标会被覆盖。求各位大侠指点一二，小弟感激不尽~
代码如下：
package com.maxseq;/**
* @author Mourinho
* 2011.6.5
*/
public class MaxSeq {
public static final long NS = 1000000000; //毫秒到秒转换的数量级
private int[] seq;
private int startIndex = 0;
private int endIndex = 0;
private double time = 0;//程序段运行时间
public MaxSeq(int[] seq){
this.seq = seq;
}
public int[] getSeq() {
return seq;
} public int getEndIndex() {
return endIndex;
} public int getStartIndex() {
return startIndex;
} public double getTime(){
return time;
}
/*
* O(NlogN)算法，采用分治法进行计算,N = 10^7时，时间为60秒左右
*/
public int findMaxSum02(int low,int high,int[] seq){
long startTime = System.nanoTime();
if(low == high){
if(seq[low] > 0)
return seq[low];
else
return 0;
}
int center = (low + high) / 2;
int leftMax = findMaxSum02(low,center,seq);
int rightMax = findMaxSum02(center + 1,high,seq);
int leftSum = 0,leftBodyMax = 0,leftIndex = center;
for(int i = center;i >= low;i--){
leftSum += seq[i];
if(leftSum >= leftBodyMax){
leftBodyMax = leftSum;
leftIndex = i;
}
}
int rightSum = 0,rightBodyMax = 0,rightIndex = center + 1;
for(int i = center + 1;i <= high;i++){
rightSum += seq[i];
if(rightSum >= rightBodyMax){
rightBodyMax = rightSum;
rightIndex = i;
}
}
int maxSum;
if(leftMax > rightMax){
maxSum = leftMax;
//下标未解决
}
else{
maxSum = rightMax;
//下标未解决
}
if((leftBodyMax + rightBodyMax) > maxSum){
maxSum = leftBodyMax + rightBodyMax;
startIndex = leftIndex;
endIndex = rightIndex;
}
long endTime = System.nanoTime();
time = (endTime - startTime) * 1.0 / NS;
return maxSum;
}
}
通过分析，可以知道：当B[K]>0时，无论B[K]为何值，B[K]=B[K-1]+A[K]当B[K]<0时，也就是B[K]记录到一个A[J]是负的，可以把B[K]变成负的，那么B[J]记录的这一段应该截掉，应为无论后面的A[K]多大，加上个负数总不可能是最大的子段和，因此将B[K]=A[K]，重新开始记录。故动态转移方程便可得出B[K] = MAX(B[K-1]+A[K] , A[K])