CODEWITHSUNDEEP
java
Devin
Devin

Reputation: 277

Java Maximum increasingly ordered subsequence

I'm writing a program that has the user enter a string and display the maximum increasingly ordered sub sequence of characters. My program however is adding the characters into an array and creating multiple arrays equal to the length of the string.

The example I was given was:

Enter a string: Welcome

Result: Welo

My program has no errors in it, but my output when entering the string, "Welcome" is:

[W, e, l, c, o, m, e]

[W, e, l, c, o, m, e]

[W, e, l, c, o, m, e]

[W, e, l, c, o, m, e]

[W, e, l, c, o, m, e]

[W, e, l, c, o, m, e]

[W, e, l, c, o, m, e]

import java.util.ArrayList;
import java.util.Scanner;

public class orderSequence {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    // Create Scanner for input/output
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter a string: ");
    String input = sc.nextLine();
    
    ArrayList<Character> al = new ArrayList();
    
    for (int i = 0; i < input.length(); i++) {
        ArrayList<Character> list = new ArrayList<Character>();
        list.add(input.charAt(i));
        
        for(int j = i + 1; j < input.length(); j++) {
            if(input.charAt(j) > list.lastIndexOf(list)) {
                list.add(input.charAt(j));
            }
        }
        
        if (list.size() > al.size()) {
            al.clear();
            al.addAll(list);
        }
        list.clear();
    }
    
    for (int i = 0; i < al.size(); i++) {
        System.out.println(al);
    }   
    
}
}

Upvotes: 0

Views: 393

Answers (3)

Martin Fall
Martin Fall

Reputation: 121

I know that this is a dated questions, but I think that it can still benefit from some clarification. The task at hand is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

Look at the string "Welcome" in its decimal string form {87, 101, 108, 99, 111, 109, 101}. The longest increasingly ordered subsequence is {87, 101, 108, 111} or "Welo".

Upvotes: 0

Vladimir Vedernikov
Vladimir Vedernikov

Reputation: 36

Try System.out.print(al.get(i)) instead of System.out.println(al)

Upvotes: 0

Matthew Meacham
Matthew Meacham

Reputation: 403

The problem happens on the line if(input.charAt(j) > list.lastIndexOf(list)). The lastIndexOf function returns the index where the object you pass in last occurs. Well, you're passing in the list itself, and nowhere in list is one of the elements list itself. So the lastIndexOf method returns -1. Thus you do character at j > -1 which is always true, and that is why your method constantly returns the entire string in the array.

Take a look here for more information about lastIndexOf.

And the way to fix your method is to do if(input.charAt(j) > list.get(list.size() - 1)) instead

And the reason that it is repeating 4 times is because of the for loop you have at the bottom. The size of al is 4, so the for loop runs the code inside of it 4 times, so it'll print out al 4 times.

Upvotes: 2

Related Questions