字符串中单调递增连续子序列——Bash

该问题和求单调递增子序列有点像，但不一样。

其主要区别就是在于连不连续，如果不要求连续(单调递增子序列)在实现时的算法是动态规划，比较复杂。

本文描述的问题是子序列连续的问题，相比而言会简单很多，原理和求最大值是一样的。

?

具体描述为给定一个字符串，求一个子串，该子串满足：

1. 连续

2. 该子串递增

3. 是最长的单调连续递增的子串

?

例如：zxuhababcba

结果：abc

?

?

代码如下：?

?

#!/bin/bash## the input str for testinputStr="zxuhababcba";strLength=${#inputStr};## record the max monotone increasing sub strmaxSubStrLength=0;maxStartPos=0;## record the position of current monotone increasing sub strcurrentStartPos=0;## find the resultfor((i=1;i<strLength;i++))do    j=$((i-1));    if [ "${inputStr:$i:1}" \< "${inputStr:$j:1}"  ]; then        currentSubStrLength=$((i-currentStartPos));        if [ $currentSubStrLength -gt $maxSubStrLength  ]; then            maxSubStrLength=$currentSubStrLength;            maxStartPos=$currentStartPos;        fi            currentStartPos=$i;    fidonelastLength=$((strLength-currentStartPos));if [ $lastLength -gt $maxSubStrLength ]; then    maxSubStrLength=$lastLength;    maxStartPos=$currentStartPos;fiecho    "original string is    : ${inputStr}";echo -n "max increasing subStr : "for((i=0;i<$maxStartPos;i++))do    echo -n " ";doneecho "${inputStr:$maxStartPos:$maxSubStrLength}";

?

?

?

在扫描过程中，记下目前为止最长的单调递增序列的开始和长度，并在当扫描中出现“拐弯”情况时，将新的递增子序列与当前记录中的最长单调递增子序列比较。

?

运行结果为：

?

?

?

该方法和给定一个数组，求数组中最大元素的方法是一回事。

?

此外，如果你想求最长单调递减子序列，则只需要改变上述代码中的一个字符就可以了，你知道是哪个吗？哈哈^_^

?

?欢迎来拍！！！