(maximum increasingly ordered subsequence) Write a program that prompts the user

Question

(maximum increasingly ordered subsequence) Write a program that prompts the user to enter a string and displays the maximum increasingly ordered subsequence of characters. Analyze then time complexitty of your program.

Here is the code, if I enter welcome, it will output elo. it should output welo. can you fix it

import java.util.Scanner;

public class Max_Inc_Ord_Sub
{
public static void main(String[] args)//main method
{
Scanner input = new Scanner(System.in); //import scanner
System.out.println("Enter a string: ");

String s = input.next();
long start = System.nanoTime();

System.out.println(maxSubstring(s));//maxsubstring method
long end = System.nanoTime();

System.out.println("Time Complexity " + (end - start) / 1.0e6 + " ms ");
}
public static String maxSubstring(String s)//increasing substring method
{
int[] max = new int[s.length()];
int[] pre = new int[s.length()];
for(int i = 0; i < s.length(); i++)
{
pre[i] = -1;
for(int j = i - 1; j >= 0; j--)
{
if (s.charAt(i) > s.charAt(j) && max[i] < max[j] + 1)
{
max[i] = max[j] + 1;
pre[i] = j;
}
}
}
int maxL = max[0];//assign value
int index = 0;
for(int i = 0; i < s.length(); i++)
{
if (maxL < max[i])
{
maxL = max[i];
index = i;
}
}
char[] chars = new char[maxL + 1];//
int i = maxL;
while (index != -1)
{
chars[i] = s.charAt(index);
i--;
index = pre[index];
}
return new String(chars);
}
}

Explanation / Answer

there is nothing wrong with the program according to my testing.

If you have entered 'W'elcome then the answer is fine Welo

as ASCII value of capital 'w' is lessthan the e.

if you enter welcome then w is not included

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.