문자열에서 가장 길게 증가하는 서브 시퀀스를 어떻게 얻을 수 있습니까?

Question

저는 Java 기술에 녹초가 있습니다.하지만 사용자에게 문자열을 입력하라는 메시지를 표시하고 순서가 지정된 하위 시퀀스를 늘리는 최대 길이를 표시하는 프로그램을 작성하려고했습니다. 예를 들어, 사용자가 Welcome을 입력하면 프로그램은 Welo을 출력합니다. 사용자가 WWWWelllcommmeee을 입력하면 프로그램은 여전히 ​​Welo을 출력합니다. 나는이 일을 많이 해왔지만 그것이해야하는 일을하지 않고 있으며 솔직히 왜 그랬는지에 관해서는 분실하고 있습니다.

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

public class Stuff { 

public static void main(String[] args) { 
    Scanner input = new Scanner(System.in); 
    System.out.println("Please enter a string. "); 
    String userString = input.next(); 
    ArrayList charList = new ArrayList(); 
    ArrayList finalList = new ArrayList(); 
    int currentLength = 0; 
    int max = 0; 

    for(int i = 0; i < userString.length(); i++){ 
     charList.add(userString.charAt(i)); 

     for(int j = i; j < userString.length(); j++){ 
      int k=j+1; 
      if(k < userString.length() && userString.charAt(k) > userString.charAt(j)){ 
       charList.add(userString.charAt(j)); 
       currentLength++; 
      } 
     } 
    } 

    if(max < currentLength){ 
     max = currentLength; 
     finalList.addAll(charList); 
    } 

    for (int i = 0; i < finalList.size(); i++){ 
     char item = (char) finalList.get(i); 
     System.out.print(item); 
    } 

    int size1 = charList.size(); 
    int size2 = finalList.size(); 
    System.out.println(""); 
    System.out.println("Size 1 is: " + size1 + " Size 2 is : " + size2);  
    } 
} 

내 코드, 만약 I Welcome 입력, 출력 WWeceeclcccome.

누군가 내가 뭘 잘못하고 있는지에 대한 조언이 있습니까?

Answer 1

이러한 경우 키보드에서 벗어나 구현하려는 알고리즘에 대해 생각하는 경향이 있습니다. 처음에는 말로 설명하십시오.

입력 문자열의 각 문자 다음에 오른쪽의 문자를 추가하여 해당 문자의 후순위와 함께 올바른 알파벳순으로 된 개별 문자 목록을 구성합니다. 합계

W W e c 
e e c 
l c 
c c 
o 
m 
e 

: 입력 "시작"은이 수평에서 수직 내부 루프 외부 루프 보여주는 축적 출력된다는 뜻 WWeceeclccome을

I이 논리를 볼 수

Answer 2

이행. 다음은 O (nlogn) 시간에 실행되는 더 빠른 솔루션입니다.

import java.util.Scanner; 

public class Stuff 
{ 
    //return the index of the first element that's not less than the target element 
    public static int bsearch(char[] arr, int size, int key) 
    { 
     int left = 0; 
     int right = size - 1; 
     int mid; 
     while (left <= right) 
     { 
      mid = (left + right)/2; 
      if(arr[mid] < key) 
       left = mid + 1; 
      else 
       right = mid - 1; 
     } 
     return left; 
    } 

    public static void main(String[] args) 
    { 
     Scanner input = new Scanner(System.in); 
     System.out.println("Please enter a string: "); 
     String userString = input.next(); 


     char[] maxArr = new char[userString.length()]; 
     char[] precedent = new char[userString.length()]; 
     maxArr[0] = userString.charAt(0); 
     precedent[0] = userString.charAt(0); 
     int len = 1; 
     for(int i = 1; i < userString.length(); i++) 
     { 
      if(userString.charAt(i) > maxArr[len - 1]) 
      { 
       maxArr[len] = userString.charAt(i); 
       precedent[len] = userString.charAt(i); 
       len++; 
      } 
      else 
       maxArr[bsearch(maxArr, len, userString.charAt(i))] = userString.charAt(i); 
     } 

     //System.out.println(len); 
     for(int i = 0; i < len; i++) 
      System.out.print(precedent[i]); 

    } 

} 

Answer 3

의 I/P는 다음 abcbcbcd 경우 의미 사전 편찬 순서 동적 프로그래밍 O (N^2)를 사용하여 O/P가 abcccd, abbbcd, abbccd하지만 O 사전 편찬 순서에 따라/P가 abbbcd 될 수있다.

public static String longestIncreasingSubsequence(String input1) { 
    int dp[] = new int[input1.length()]; 
    int i,j,max = 0; 
    StringBuilder str = new StringBuilder(); 

    /* Initialize LIS values for all indexes */ 
    for (i = 0; i < input1.length(); i++) 
     dp[i] = 1; 

    /* Compute optimized LIS values in bottom up manner */ 
    for (i = 1; i < input1.length(); i++) 
     for (j = 0; j < i; j++) 
       if (input1.charAt(i) >= input1.charAt(j) && dp[i] < dp[j]+1) 
        dp[i] = dp[j] + 1; 

    /* Pick maximum of all LIS values */ 
    for (i = 0; i < input1.length(); i++) { 
     if (max < dp[i]) { 
      max = dp[i]; 
      if (i + 1 < input1.length() && max == dp[i+1] && input1.charAt(i+1) < input1.charAt(i)) { 
       str.append(input1.charAt(i+1)); 
       i++; 
      } else { 
       str.append(input1.charAt(i)); 
      } 
     } 
    } 
    return str.toString(); 
}