最大单调子序列(Maximum Monotone Subsequence )-如果一个数列中第i个元素最少也和第i - 1个元素一样大，那么该序列单调递增。求字符串的一个最大单调递增子序列。
示例：
输入：s = "subsequence"
输出：beee
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> 设dp[i]表示字符串s的前i个字符的最大单调递增子序列的长度。
当s[i] >= s[k]时，有 d p [ i ] = m a x ( d p [ k ] ) + 1 dp[i] = max(dp[k]) + 1 dp[i]=max(dp[k])+1，其中 1 <= k < i
否则 d p [ i ] = 0 dp[i] = 0 dp[i]=0，其中1 <= k < i 。
总结为如下方程：
d
p
[
i
]
=
{
m
a
x
(
d
p
[
k
]
)
+
1
,
s
[
i
]
≥
s
[
k
]
1
,
s
[
i
]
<
s
[
k
]
dp[i] = class="MathJax_Display">
此状态方程理解起来很简单。
显然dp[0]初始化为0。
/**
* 最大单调子序列
*
* @author hh
* @date 2021-5-16 20:52
*/
public class MaxMonotoneSubsequence {
/**
* 求字符串的最大单调子序列
*
* @param s 字符串
* @return 最大单调子序列组成的字符串
*/
public String maxMonotoneSubsequence(String s){
int[] dp = new int[s.length() + 1];
//记录最大单调子序列的数组索引
int[] indexes = new int[s.length() + 1];
//初始化dp[0]为0
dp[0] = 0;
indexes[0] = -1;
for(int i = 1; i <= s.length(); i++){
int parentIndex = 0;
for(int k = 1; k < i; k++){
if(s.charAt(i-1) >= s.charAt(k-1) && dp[i] <= dp[k]){
dp[i] = dp[k];
parentIndex = k;
}
}
indexes[i] = parentIndex;
dp[i] += 1;
}
return findPath(s,indexes, this.getMaxValueIndex(dp,Arrays.stream(dp).max().getAsInt()) );
}
public int getMaxValueIndex(int[] dp,int maxValue){
for(int i = dp.length - 1; i >=0; i-- ){
if(dp[i] == maxValue){
return i;
}
}
return 0;
}
/**
* 构建一条最长路径
*
* @param s 源字符串
* @param indexes 索引数组
* @param maxDepth 最长数
* @return 子序列字符串
*/
public String findPath(String s,int[] indexes,int maxDepth){
LinkedList<Character> characterList = new LinkedList<>();
while (maxDepth != 0){
characterList.addFirst(s.charAt(maxDepth - 1));
maxDepth = indexes[maxDepth];
}
return characterList.stream().map(String::valueOf).collect(Collectors.joining());
}
public static void main(String[] args){
String s = "subsequence";
MaxMonotoneSubsequence maxMonotoneSubsequence = new MaxMonotoneSubsequence();
System.out.println(maxMonotoneSubsequence.maxMonotoneSubsequence(s));
}
}
class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">
评论记录：
回复评论：