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

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

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

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

 

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

1. 连续

2. 该子串递增

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

 

例如：zxuhababcba

结果：abc

 

 

代码如下： 

 

#!/bin/bash

## the input str for test
inputStr="zxuhababcba";
strLength=${#inputStr};

## record the max monotone increasing sub str
maxSubStrLength=0;
maxStartPos=0;
## record the position of current monotone increasing sub str
currentStartPos=0;

## find the result
for((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;
    fi
done

lastLength=$((strLength-currentStartPos));
if [ $lastLength -gt $maxSubStrLength ]; then
    maxSubStrLength=$lastLength;
    maxStartPos=$currentStartPos;
fi

echo    "original string is    : ${inputStr}";
echo -n "max increasing subStr : "
for((i=0;i<$maxStartPos;i++))
do
    echo -n " ";
done
echo "${inputStr:$maxStartPos:$maxSubStrLength}";

 

 

 

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

 

运行结果为：

 

 

 

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

 

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

 

 欢迎来拍！！！