# 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

```Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. ```

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

`array[i]= Math.max(array[i],1+array[j]);`

## 解法：

```     public int lengthOfLIS(int[] nums) {
if(nums == null|| nums.length ==0) return 0;
int [] array = new int[nums.length];
for (int i=0;i<array.length;i++){
array[i] = 1;
}

// array[i]表示以array[i]为结尾的最长上升子序列的长度。
for (int i = 1;i<nums.length;i++){
for (int j = 0;j<i;j++){
if (nums[j] < nums[i]){
array[i] = Math.max(array[i],1+array[j]);
}
}
}

int res = 1;
for (int i = 0;i<array.length;i++){
res = Math.max(res,array[i]);
}
return res;
}```

# 二.求最长的公共子串

## 解法一：

```public static int [][] longestSubString(String str1,String str2){
char [] chars1 = str1.toCharArray();
char [] chars2 = str2.toCharArray();
int [][] dp = new int[chars1.length][chars2.length];
for (int i=0;i<str1.length();i++){
if (chars2[0] == chars1[i]){
dp[i][0] = 1;
}
}

for (int j = 1;j<str2.length();j++){
if (chars1[0] == chars2[j]){
dp[0][j] = 1;
}
}

for (int i = 1;i<chars1.length;i++){
for (int j = 1;j<chars2.length;j++){
if (chars1[i] == chars2[j]){
dp[i][j] = dp[i-1][j-1] + 1;
}
}
}
return dp;
}

public static String lcst1(String str1,String str2){
if (str1==null||str2==null||str1.equals("")||str2.equals("")){
return "";
}
int[][] dp = longestSubString(str1,str2);
int end = 0;
int max = 0;
for (int i = 0;i<str1.length();i++){
for (int j = 0;j<str2.length();j++){
if (dp[i][j]>max){
end = i;
max = dp[i][j];
}
}
}
return str1.substring(end-max+1,end+1);
}```

longestSubString（）函数获取dp数组：

```1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 2 0 0 0 0
0 0 0 3 0 0 0
0 0 0 0 4 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0 ```

# 三.求最长的公共子序列

"123456"或"12C4B6"，都是最长的公共子序列。

S1[m] == S2[n]，则有：LCS(m,n) = 1 +LCS(m-1,n-1)

S1[m] != S2[n]，则有：LCS(m,n) =max(LCS(m-1,n),LCS(m,n-1))

```public int LCS(String str1, String str2){
int[][] dp = new int[str1.length()+1][str2.length()+1];
for (int i = 1 ;i<=str1.length();i++){
for (int j = 1;j<=str2.length();j++){
if (str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
}
else{
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
}
}
}
return dp[str1.length()][str2.length()];
}```

```String str1 = "13456778";
String str2 = "357486782";```

```0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 1 1 2 2 2 2 2 2
0 1 2 2 2 2 2  2 2
0 1 2 2 2 2 3 3 3 3
0 1 2 3 3 3 3 4 4 4
0 1 2 3 3 3 3 4 4 4
0 1 2 3 3 4 4 4 5 5 ```

1. S1[i] != S2[j] ，且dp[i-1][j] = dp[i][j-1] 这种存在分支的情况，这里请都选择一个方向（之后遇到这样的情况，也选择相同的方向）
2. 如果s1[i] == s2[j] 就跳转到dp[i - 1][j - 1],如果s1[i] != s1[j], 就向前找或向上找（只能一个方向）

```    int i = str1.length();
int j = str2.length();
while (i>0 && j>0){
if (str1.charAt(i-1) != str2.charAt(j-1)){
if (dp[i][j-1]>dp[i-1][j]){
j--;
}else{
i--;
}
} else {     //S1[i] == S2[j],  c[i - 1][j - 1]
result += str1.charAt(i-1);
i--;
j--;
}

}
return result;
}```

```public String LCS(String str1, String str2){
String result = "";
int[][] dp = new int[str1.length()+1][str2.length()+1];
for (int i = 1 ;i<=str1.length();i++){
for (int j = 1;j<=str2.length();j++){
if (str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
}
else{
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
}
}
}
int i = str1.length();
int j = str2.length();
while (i>0 && j>0){
if (str1.charAt(i-1) != str2.charAt(j-1)){
if (dp[i][j-1]>dp[i-1][j]){
j--;
}else{
i--;
}
} else {     //S1[i] == S2[j],  c[i - 1][j - 1]
result += str1.charAt(i-1);
i--;
j--;
}

}
return result;
}```

0 条评论

## 相关文章

40040

31450

35690

### 实训day03--循环，内存，数组

2018.06.06 1.switch用法 Scanner sc = new Scanner(System.in); while(t...

13630

12830

### 递归与伪递归区别，Python 实现递归与尾递归

递归函数在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函 数。(1) 递归就是在过程或函数里调用自身。(2) 在使...

38170

73480

9220

19690

### Spark2.x学习笔记：2、Scala简单例子

2、 Scala简单例子 参考教程:https://yq.aliyun.com/topic/69 2.1 交互式编程 spark-shell是Spark交互式...

57180