求解最大子序列、最长递增子序列、
最长公共子串 、最长公共子序列
最大子序列：
找出由数组成的一维数组中和最大的连续子序列。
最长递增子序列(Longest Increasing Subsequence)：
设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列
Lin
=<aK1,ak2,…,
akm
>，其中k1<k2<…<km且aK1<=ak2<=…<=
akm
。求最大的m值。
最长公共子串LCS：
找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。
最长公共子序列：
最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的。
Java代码：
public
class
Subsequence {
public
static
int
count
;
public
static
void
main(String[] args) {
testmaxSubsequence();
testLongestIncreasingSubsequence();
testlongestCommonString();
testlongestCommonSubsequence();
}
//
最大子序列
是要找出由数组成的一维数组中和最大的连续子序列。
//
比如
{5,-3,4,2}
的最大子序列就是
{5,-3,4,2}
，它的和是
8,
达到最大；
//
而
{5,-6,4,2}
的最大子序列是
{4,2}
，它的和是
6
。
//
求解方法：创建一个同样大小的数组，数组中的每一个位置记录该位置前面的最大的连续子序列和，
//
该位置是否要继续前面的最大的连续子序列就要看该位置前面的最大的连续子序列和是否大于
0,
//
如果大于等于
0
，则加入该位置前面的最大的连续子序列，该位置值为前面的最大的连续子序列和加上该位置对应的数组值，
//
如果小于
0
，则不加入该位置前面的最大的连续子序列，以自己为新的最大的连续子序列，该位置值为该位置对应的数组值。
public
static
void
maxSubsequence(
int
[] array) {
if
(array.
length
<= 0)
return
;
int
[] sum =
new
int
[array.
length
];
int
maxSum = array[0];
for
(
int
i = 0; i < array.
length
; i++) {
if
(i == 0)
sum[i] = array[i];
else
{
if
(sum[i – 1] >= 0)
sum[i] = sum[i – 1] +array[i];
else
sum[i] = array[i];
}
if
(maxSum < sum[i])
maxSum = sum[i];
}
System.
out
.println(
“MaxSum:\t”
+ maxSum);
System.
out
.println(
“——————–”
);
for
(
int
i = 0; i < sum.
length
; i++) {
if
(sum[i] == maxSum) {
int
j = i;
while
(j >= 0 && sum[j] >= 0)
j–;
System.
out
.print(
“MaxSubsequence:\t”
);
for
(j++; j <= i; j++)
System.
out
.print(array[j] +
” ”
);
System.
out
.println();
System.
out
.println(
“——————–”
);
}
}
System.
out
.println(
“******************”
);
}
public
static
void
testmaxSubsequence() {
int
[] array;
array =
new
int
[] { 5, -3, 4, 2 };
maxSubsequence
(array);
array =
new
int
[] { 5, -6, 4, 2 };
maxSubsequence
(array);
array =
new
int
[] { 5, -6, 4, 2, -10, 5, -6, 4, 2 };
maxSubsequence
(array);
}
//
最长递增子序列(Longest Increasing Subsequence)
// 设L=<a1,a2,…,an>是n个不同的实数的序列，L的递增子序列是这样一个子序列
Lin
=<aK1,ak2,…,
akm
>，
// 其中k1<k2<…<km且aK1<=ak2<=…<=
akm
。求最大的m值。
//
最长递增子序列
O
（
n^2
）求解算法：
//
创建一个同样大小的数组，用于记录当前位置的值从头开始到该位置对应的最长递增子序列的长度
//
该数组中的值计算方法为遍历该位置左边的所有记录数值，找到最大的记录数，当前位置值为找到的最大记录数加
1.
//
如果要输出最长递增序列，需要另外创建一个同样大小的数组，用于记录构成当前位置数值对应最长递增子序列的前面位置。
public
static
void
longestIncreasingSubsequence(
int
[] array) {
if
(array.
length
<= 0)
return
;
//
记录当前位置对应的最长递增子序列的长度
int
[] incLen =
new
int
[array.
length
];
int
maxLen;
//
遍历数组
//
遍历数值需要
O(n),
嵌套求当前位置前面的最长递增子序列的长度需要
O(n)
，故
O
（
n^2
）
for
(
int
i = 0; i < array.
length
; i++) {
//
找到当前位置前面的最长递增子序列的长度
maxLen = 0;
for
(
int
j = 0; j < i; j++) {
if
(maxLen < incLen[j] && array[i]>= array[j])
maxLen = incLen[j];
}
//
当前位置对应的最长递增子序列的长度为前面的最长递增子序列的长度加
1
incLen[i] = maxLen + 1;
}
//
遍历记录最长递增子序列的长度数组，找到最长长度
maxLen = 0;
for
(
int
i = 0; i < array.
length
; i++) {
if
(maxLen < incLen[i])
maxLen = incLen[i];
}
//
打印出所有的最长递增子序列。最长递增子序列可能包含多个，用递归方法求解。
//
求解方法：最长长度的位置对应为最长递增子序列的最后一个位置，可能有多个。
//
递归求解已知最长递增子序列位置的前一个位置，遍历该位置左边的所有位置，
//
长度等于当前长度减
1
并且数值小于等于当前数值的为前一位置，可能有多个。
System.
out
.println(
“*******************”
);
System.
out
.println(
“Array(IncreaseLength)”
);
for
(
int
i = 0; i < array.
length
; i++)
System.
out
.print(array[i] +
“(”
+ incLen[i] +
“) ”
);
System.
out
.println();
System.
out
.println(
“LongestIncreasingSubsequence:\t”
);
System.
out
.println(
“MaxLength:\t”
+ maxLen);
System.
out
.println(
“————————”
);
int
[] stack =
new
int
[array.
length
];
int
top = 0;
count
= 0;
for
(
int
i = 0; i < array.
length
; i++) {
if
(maxLen == incLen[i]) {
stack[top++] = array[i];
printLonIncSubInfo
(array,incLen, i, stack, top);
top–;
}
}
}
//
递归求解已知最长递增子序列位置的前一个位置
public
static
void
printLonIncSubInfo(
int
[] array,
int
[] incLen,
int
index,
int
[] stack,
int
top) {
//
当最长递增子序列对应位置长度为
1
，则为起点，输出。可能含有多个起点
if
(incLen[index] == 1) {
System.
out
.println(
“Num:\t”
+ (++
count
));
for
(
int
i = top – 1; i >= 0; i–)
System.
out
.print(stack[i] +
” ”
);
System.
out
.println();
System.
out
.println(
“————————”
);
}
for
(
int
i = index – 1; i >= 0; i–) {
if
(incLen[i] == incLen[index] – 1 &&array[index] >= array[i]) {
stack[top++] = array[i];
printLonIncSubInfo
(array,incLen, i, stack, top);
top–;
}
}
}
//
最长递增子序列
O
（
nlogn
）求解算法：
//
优化方法在寻找当前位置前面的最长长度，
//
记录当前长度对应的最长递增子序列的数值，当出现冲突，存储最右边的值。
//
采用二分查找的方法，将
O(n)
降到
O(
logn
)
//
该优化算法只能最长递增子序列的长度，无法得到最长递增子序列。
public
static
void
longestIncreasingSubsequenceOpt(
int
[] array) {
if
(array.
length
<= 0)
return
;
//
记录当前长度对应的最长递增子序列的数值
int
[] lenVal =
new
int
[array.
length
];
int
lenCount;
lenCount = 0;
//
遍历数组
//
遍历数值需要
O(n),
嵌套求当前位置前面的最长递增子序列的长度需要
O(log(n))
，故
O(
nlog
(n))
for
(
int
i = 0; i < array.
length
; i++) {
//
找到比当前值大并且最接近当前值的对应最长递增子序列长度的位置
int
sta = 0;
int
end = lenCount – 1;
int
mid;
while
(sta < end) {
mid = sta + (end – sta) / 2;
if
(array[i] > array[lenVal[mid]]) {
sta = mid + 1;
}
else
if
(array[i] < array[lenVal[mid]]) {
end = mid;
}
else
{
sta = mid + 1;
}
}
if
(sta >= lenCount) {
lenVal[lenCount++] = i;
}
else
if
(array[lenVal[sta]] > array[i]) {
lenVal[sta] = i;
if
(sta == lenCount)
lenCount++;
}
else
{
lenVal[sta + 1] = i;
if
(sta + 1 == lenCount)
lenCount++;
}
}
System.
out
.println(
“*******************”
);
System.
out
.println(
“LongestIncreasingSubsequence Length:\t”
+ lenCount);
System.
out
.println(
“*******************”
);
}
public
static
void
testLongestIncreasingSubsequence() {
int
[] array =
new
int
[] { 1, -1, 3, 10, 5, 4, 7, 2, 9, 5, 5 };
longestIncreasingSubsequence
(array);
longestIncreasingSubsequenceOpt
(array);
}
//
最长公共子串LCS：
//
找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。
//
解法：将一个字符串作横坐标，一个字符串作纵坐标，构成一个二维矩阵表，
//
矩阵中的值如果满足横坐标值等于纵坐标值为
true
，否则为
false
。
//
最长公共子串为左上到右下的对角线最长的连续值为
true
的解。
//
求解原理是错位字符串，比较连续最长子串。
//
优化方法将矩阵设置成整型二维数组，在填充数值时加上右上角数值。
//
最长公共串为二位数组中值最大的位置右上角到
1
的位置。
//
例如：求
abcde
和
ebcda
最长公共子串。
// e b c da
// a 0 0 00 1
// b 0 1 00 0
// c 0 0 20 0
// d 0 0 03 0
// e 1 0 00 0
public
static
void
longestCommonString(String str1, Stringstr2) {
char
[] array1 = str1.toCharArray();
char
[] array2 = str2.toCharArray();
int
[][] matrix =
new
int
[array1.
length
][array2.
length
];
int
maxLen = 0;
for
(
int
i = 0; i < array1.
length
; i++) {
matrix[i] =
new
int
[array2.
length
];
for
(
int
j = 0; j < array2.
length
; j++) {
if
(array1[i] == array2[j]) {
//
防止越界
if
(i – 1 >= 0 && j – 1 >= 0)
matrix[i][j] = matrix[i- 1][j – 1] + 1;
else
matrix[i][j] = 1;
if
(matrix[i][j] > maxLen)
maxLen = matrix[i][j];
}
else
matrix[i][j] = 0;
}
}
//
输出
int
count = 0;
System.
out
.println(
“*******************”
);
System.
out
.println(
“longestCommonString”
);
System.
out
.println(
“String1:\t”
+ str1);
System.
out
.println(
“String2:\t”
+ str2);
System.
out
.println(
“——————-”
);
for
(
int
i = 0; i < array1.
length
; i++) {
for
(
int
j = 0; j < array2.
length
; j++) {
if
(maxLen == matrix[i][j]) {
System.
out
.println(
“Num:\t”
+ (++count));
System.
out
.println(
“String1 Location:\t”
+ (i – maxLen + 1));
System.
out
.println(
“String2 Location:\t”
+ (j – maxLen + 1));
for
(
int
k = maxLen – 1; k >= 0; k–)
System.
out
.print(array1[i -k]);
System.
out
.println();
System.
out
.println(
“——————-”
);
}
}
}
}
public
static
void
testlongestCommonString() {
longestCommonString
(
“abcdefgabc”
,
“abc”
);
longestCommonString
(
“abcdeabd”
,
“abccdeae”
);
longestCommonString
(
“abcde”
,
“ebcda”
);
}
//
最长公共子序列
//
最长公共子序列与最长公共子串的区别在于最长公共子序列不要求在原字符串中是连续的
，
//
比如
ADE
和
ABCDE
的最长公共子序列是
ADE
。
//
字符串编辑距离是同类问题。
//
动态规划求解：
// C1
是
S1
的最右侧字符，
C2
是
S2
的最右侧字符，
S1‘
是从
S1
中去除
C1
的部分，
S2′
是从
S2
中去除
C2
的部分。
//LCS(S1,S2)
等于下列
3
项的最大者：
//
（
1
）
LCS
（
S1
，
S2’
）
//
（
2
）
LCS
（
S1’
，
S2
）
//
（
3
）
LCS
（
S1’
，
S2’
）
—
如果
C1
不等于
C2
；
LCS
（
S1′
，
S2′
）
+C1–
如果
C1
等于
C2
；
//
边界终止条件：如果
S1
和
S2
都是空串，则结果也是空串。
//
gccctagcg
和
gcgcaatg
求解：
// g c c c t a g c g
// g 1 1 1 1 1 1 1 1 1
// c 1 2 2 2 2 2 2 2 2
// g 1 2 2 2 2 2 3 3 3
// c 1 2 3 3 3 3 3 4 4
// a 1 2 3 3 3 4 4 4 4
// a 1 2 3 3 3 4 4 4 4
// t 1 2 3 3 4 4 4 4 4
// g 1 2 3 3 4 4 5 5 5
public
static
void
longestCommonSubsequence(String str1, Stringstr2) {
if
(str1.length() == 0 || str2.length() == 0)
return
;
char
[] array1 = str1.toCharArray();
char
[] array2 = str2.toCharArray();
int
[][] matrix =
new
int
[array1.
length
][array2.
length
];
int
max, maxLcs;
maxLcs = 0;
for
(
int
i = 0; i < array1.
length
; i++) {
matrix[i] =
new
int
[array2.
length
];
for
(
int
j = 0; j < array2.
length
; j++) {
max = 0;
if
(i – 1 >= 0 && matrix[i – 1][j]> max) {
max = matrix[i – 1][j];
}
if
(j – 1 >= 0 && matrix[i][j – 1]> max) {
max = matrix[i][j – 1];
}
if
(array1[i] == array2[j]) {
if
(i – 1 >= 0 && j – 1 >= 0
&& matrix[i- 1][j – 1] + 1 > max)
max = matrix[i – 1][j -1] + 1;
else
if
(1 > max)
max = 1;
}
else
{
if
(i – 1 >= 0 && j – 1 >= 0
&& matrix[i- 1][j – 1] + 1 > max)
max = matrix[i – 1][j -1];
else
if
(0 > max)
max = 0;
}
matrix[i][j] = max;
if
(maxLcs > max)
max = maxLcs;
}
}
count
=0;
System.
out
.println(
“*******************”
);
System.
out
.println(
“longestCommonSubsequence”
);
System.
out
.println(
“String1:\t”
+ str1);
System.
out
.println(
“String2:\t”
+ str2);
System.
out
.print(
” ”
);
for
(
int
j = 0; j < array2.
length
; j++) {
System.
out
.print(array2[j] +
” ”
);
}
System.
out
.println();
for
(
int
i = 0; i < array1.
length
; i++) {
System.
out
.print(array1[i] +
” ”
);
for
(
int
j = 0; j < array2.
length
; j++) {
System.
out
.print(matrix[i][j]+
” ”
);
}
System.
out
.println();
}
System.
out
.println(
“——————-”
);
char
[] stack =
new
char
[array1.
length
> array2.
length
? array1.
length
: array2.
length
];
printLongestCommonSubsequence
(array1,array2, matrix,
array1.
length
– 1, array2.
length
– 1, stack, 0);
System.
out
.println(
“*******************”
);
}
public
static
void
printLongestCommonSubsequence(
char
[] array1,
char
[] array2,
int
[][] matrix,
int
i,
int
j,
char
[] stack,
int
top) {
if
(matrix[i][j] == 1 && array1[i] ==array2[j]) {
stack[top++] = array1[i];
System.
out
.println(
“Num:\t”
+ (++
count
));
for
(
int
k = top – 1; k >= 0; k–)
System.
out
.print(stack[k]);
System.
out
.println();
System.
out
.println(
“——————-”
);
top–;
}
if
(i – 1 >= 0 && j – 1 >= 0) {
if
(array1[i] == array2[j]) {
stack[top++] = array1[i];
printLongestCommonSubsequence
(array1,array2, matrix, i – 1,
j – 1, stack, top);
top–;
}
else
if
(matrix[i – 1][j – 1] == matrix[i][j]) {
printLongestCommonSubsequence
(array1,array2, matrix, i – 1,
j – 1, stack, top);
}
}
if
(i – 1 >= 0 && matrix[i – 1][j]== matrix[i][j]) {
printLongestCommonSubsequence
(array1,array2, matrix, i – 1, j,
stack, top);
}
if
(j – 1 >= 0 && matrix[i][j – 1]== matrix[i][j]) {
printLongestCommonSubsequence
(array1,array2, matrix, i, j – 1,
stack, top);
}
}
public
static
void
testlongestCommonSubsequence() {
longestCommonSubsequence
(
“gcgcaatg”
,
“gccctagcg”
);
longestCommonSubsequence
(
“abcdef”
,
“ghijkl”
);
longestCommonSubsequence
(
“abcdef”
,
“adefbc”
);
}
}
下载地址：