提供一种思路,不一定很好。
先思考单一数列中按顺序取若干元素的最大值问题。
这个问题的一种固定解法就是:在可以选择的范围内,选择最大的元素;如果有多个最大元素,选择最靠左的那个。
举例,在2868734952中选择5个数字构成最大值。
首先,第一个元素只能在最左边的"286873"中选出(因为再向右选的话剩余元素就凑不出4个数字了,也就是最后的结果凑不出5位数)。
在"286873"中最大元素是8,我们选择尽可能靠左的“8”输出,然后剩下的序列变成"68734952"
下一个元素只能在"68734"中选出,选8,剩下序列"734952"
第3个元素只能在"7349"中选出,选9,剩下序列"52"
依次类推。
最后结果是88952。
双数列要复杂的多,但是可以用类似的思路来处理它们。
假设有数列A(1,n)={a1, a2, ... an}和B(1,m)={b1,b2,...,bm},从中要选取K个元素。怎么做呢?
显然,第1个元素要么从A(1,n)中给出,要么从B(1,m)中给出。
所以,我们可以构造数列(A(1,n),B(1,m))={a1,a2,...,an,b1,b2,...bm},从允许的范围内挑出最靠左边的最大元素f1(这个时候挑出的元素是A中的可能性大)。
我们再构造一个数列(B(1,m),A(1,n))={b1,b2,...,bm,a1,a2,...an},从允许的范围内挑出最靠左边的最大元素f2(这个时候挑出的元素是B中的可能性大)。
如果f1<>f2,选择大的值输出,然后把A或B中该值以及左边的内容切除;
如果f1=f2,且f1、f2都是A或都是B中的元素,则f1和f2必是同一个元素,把该元素输出,并在对应的数列中切除f1以及左边的所有元素;
如果f1=f2,但是f1是ai, f2是bj,则当前步骤无法判断哪个值更合适,需要依次递归进行后续的切割后方能判断。
大致的核心伪代码如下(偷懒起见,用char数组代表数列,用String代表输出的子序列):
char[] A=....;
char[[ B=....;
int getMaxIndexInA(int ai, int bj, int L) {
//在{ai, ai+1,... an, bj, bj+1, ... bm}中,排除最右边的L-1个元素后,找最左边最大的元素,如果该元素属于A,返回其序号,否则返回-1。
}
int getMaxIndexInB(int ai, int bj, int L) {
//在{bj, bj+1, ... bm,ai, ai+1,... an}中,排除最右边的L-1个元素后,找最左边最大的元素,如果该元素属于B,返回其序号,否则返回-1。
}
//获取由序列{ai,...an}以及{bj,...,bm}之中的顺序最大子序列,返回其值。
String getSubList(int ai, int bi, int L) throws Exception{
if (L<=0) {
return "";
}
int next_A_index = getMaxIndexInA(ai, bj, L);
int next_B_index = getMaxIndexInB(ai, bj, L);
if ((next_A_index<0) && (next_B_index<0)) {
throw new Exception("找不到解");
}
if (next_A_index<0) {
String result = b[next_B_index];
result += getSubList(ai, next_B_index+1, L-1);
} else if (next_B_index<0) {
String result = a[next_A_index];
result += getSubList(next_A_index+1, bj, L-1);
} else {
String resultA = a[next_A_index];
resultA += getSubList(next_A_index+1, bj, L-1);
String resultB = b[next_B_index];
resultB += getSubList(ai, next_B_index+1, bj, L-1);
if (resutA<resultB) {
return resultB;
} else {
return resultA;
}
}
}
main () {
...
getSubList(0, 0, L);
...
}