编写一个程序，提示用户输入一个字符串，然后显示最大连续递增的有序子串。分析你的程序的时间复杂度。下面是一个运行示例：

思路：在每一刻都需要知道2个值：当前子串和当前最大子串，主循环是比较每一次移动后当前子串和当前最大子串的长度，根据情况的不同分类讨论：

设输入字符串为str， i, j 分别指向当前最大子串的首元素和尾元素，p, q 分别指向当前子串的首元素和尾元素，len = q - p + 1, 表示当前子串的长度，Lmax = j - i + 1，表示当前最大子串的长度，则有：

if(len > Lmax):

        更新最大子串

else

        if(q+1不是整个字符串最后一位 && str[q+1] >= str[q])

                q后移一位，当前子串长度+1；

        else if（q+1不是整个字符串最后一位 && str[q+1] < str[q]）

                当前子串没机会成为最大子串了，于是从q+1位重新开始；

        else

                q是str最后一位，结束循环；

用图表示：

代码如下：

import java.util.Scanner;
/*
最大连续递增有序子串*/public class E23_1 {public static void main(String[] args) {System.out.println("Enter a string:");Scanner sc = new Scanner(System.in);String str = sc.nextLine();//调用函数查找最长子串findMaxSubString(str);}public static void findMaxSubString(String str){int i, j, p, q, Lmax, len;i = j = 0;p = q = 0;while (p < str.length() && q < str.length()){Lmax = j - i + 1;len = q - p + 1;//当前字串长与当前最大字串长比较if (len <= Lmax){//若不长于最大字串，查看串尾q是否可后移if ((q+1)<str.length() && (str.charAt(q+1) >= str.charAt(q)))//可后移且子串可延长，则q后移，当前字串长度+1q += 1;else if ((q+1)<str.length() && (str.charAt(q+1) < str.charAt(q))){//可后移但子串不可延长，则从q+1开始新的当前子串q += 1;p = q;}else//q不可后移（到达str最后一位），退出循环得到最长子串break;}else {//当前子串长于最大子串，更新最大子串为当前子串i = p;j = q;}}//输出最长子串String maxSubStr = str.substring(i, j+1);System.out.println("最长子串是：" + maxSubStr);}
}

时间复杂度：由于只遍历了一遍字符串，所以T(n) = O(n)