目录
数组中的最⻓连续⼦序列（排序+模拟）
题目解析
讲解算法原理
编写代码
字⺟收集（动态规划-路径问题）
题目解析
讲解算法原理
编写代码
数组中的最⻓连续⼦序列（排序+模拟）
题目解析
1.题目链接：数组中的最长连续子序列_牛客题霸_牛客网
2.题目描述
描述
给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）
数据范围： 1 \le n \le 10^51≤n≤105，数组中的值满足 1\le val \le 10^81≤val≤108
要求：空间复杂度 O(n)O(n)，时间复杂度 O(nlogn)O(nlogn)
示例1
输入：
[100,4,200,1,3,2]
返回值：
4
示例2
输入：
[1,1,1]
返回值：
1
备注：
1 \leq n \leq 10^51≤n≤105
1 \leq arr_i \leq 10^81≤arri≤108
讲解算法原理
解法：
算法思路：
排序+模拟
但是要注意处理数字相同的情况！
编写代码
c++算法代码：
class Solution
{
public:int MLS(vector<int>& arr) {sort(arr.begin(), arr.end());int n = arr.size(), ret = 0;for(int i = 0; i < n; ){int j = i + 1, count = 1;while(j < n){if(arr[j] - arr[j - 1] == 1){count++;j++;}else if(arr[j] - arr[j - 1] == 0){j++;}else{break;}}ret = max(ret, count);i = j;}return ret;}
};java算法代码：
import java.util.*;
public class Solution
{public int MLS (int[] arr) {Arrays.sort(arr);int n = arr.length, ret = 0;for(int i = 0; i < n; ){int j = i + 1, count = 1;while(j < n){if(arr[j] - arr[j - 1] == 1){count++;j++;}else if(arr[j] - arr[j - 1] == 0){j++;}else{break;}}ret = Math.max(ret, count);i = j;}return ret;}
}
字⺟收集（动态规划-路径问题）
题目解析
1.题目链接：字母收集_牛客题霸_牛客网
2.题目描述
描述
有一个 n*mn∗m 的矩形方阵，每个格子上面写了一个小写字母。
小红站在矩形的左上角，她每次可以向右或者向下走，走到某个格子上就可以收集这个格子的字母。
小红非常喜欢 "love" 这四个字母。她拿到一个 l 字母可以得 4 分，拿到一个 o 字母可以得 3 分，拿到一个 v 字母可以得 2 分，拿到一个 e 字母可以得 1 分。
她想知道，在最优的选择一条路径的情况下，她最多能获取多少分？输入描述：
1 \leq n,m \leq 5001≤n,m≤500
接下来的 nn 行 每行一个长度为 mm 的、仅有小写字母构成的字符串，代表矩形方阵。输出描述：
小红最大可能的得分。
示例1
输入：
3 2
ab
cd
ef输出：
1
说明：
选择下、下、右）这条路径即可，可以收集到 acef 这四个字母各一次，获得 0+0+1+0=1 分。
示例2
输入：
2 3
lle
ove输出：
11
讲解算法原理
解法：
算法思路：
基础的路径问题的dp模型。
编写代码
c++算法代码：
#include <iostream>
using namespace std;
const int N = 510;
char g[N][N];
int dp[N][N];
int m, n;
int main()
{cin >> m >> n;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){cin >> g[i][j];}}for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){int t = 0;if(g[i][j] == 'l') t = 4;else if(g[i][j] == 'o') t = 3;else if(g[i][j] == 'v') t = 2;else if(g[i][j] == 'e') t = 1;dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + t;}}cout << dp[m][n] << endl;return 0;
}Java算法代码：
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt(), m = in.nextInt();char[][] arr = new char[n + 1][m + 1];for(int i = 1; i <= n; i++){char[] s = in.next().toCharArray();for(int j = 1; j <= m; j++){arr[i][j] = s[j - 1];}}int[][] dp = new int[n + 1][m + 1];for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){int t = 0;if(arr[i][j] == 'l') t = 4;else if(arr[i][j] == 'o') t = 3;else if(arr[i][j] == 'v') t = 2;else if(arr[i][j] == 'e') t = 1;dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + t;}}System.out.println(dp[n][m]);}
}
