1+ /*********************************************************************************
2+ * (Maximum increasingly ordered subsequence) Write a program that prompts the *
3+ * user to enter a string and displays the maximum increasingly ordered *
4+ * subsequence of characters. Analyze the time complexity of your program. *
5+ *********************************************************************************/
6+ import java .util .*;
7+
8+ public class Exercise_22_02 {
9+ public static void main (String []args ) {
10+ // Create a Scanner
11+ Scanner input =new Scanner (System .in );
12+
13+ // Prompt the user to enter a string
14+ System .out .print ("Enter a string: " );
15+ String string =input .nextLine ();
16+
17+ LinkedList <Character >max =new LinkedList <>();
18+
19+ // Find the maximum increasingly ordered subsequence
20+ for (int i =0 ;i <string .length ();i ++) {
21+ LinkedList <Character >list =new LinkedList <>();
22+ list .add (string .charAt (i ));
23+ for (int j =i +1 ;j <string .length ();j ++) {
24+ if (string .charAt (j ) >list .getLast ()) {
25+ list .add (string .charAt (j ));
26+ }
27+ }
28+
29+ if (list .size () >max .size ()) {
30+ max .clear ();
31+ max .addAll (list );
32+ }
33+ list .clear ();
34+ }
35+
36+ // Display the maximum consecutive
37+ // increasingly ordered substring
38+ for (Character ch :max ) {// single loop
39+ System .out .print (ch );// Simple statement
40+ }
41+ System .out .println ();
42+ }
43+
44+ /*********************************************************************************
45+ * Analyze the time complexity of your program: *
46+ * 1 outerloop = n; *
47+ * 1 innerloop = n - 1; *
48+ * 1 simple statement = 1 *
49+ * 1 single loop * 1 simple statement = 1; *
50+ * T(n) = (n * (n - 1)) + (1 + 1); *
51+ * T(n) = O(n^2) + O(n); *
52+ * T(n) = O(n^2) Quadratic time; *
53+ *********************************************************************************/
54+ }
