Question

Part I: Maximum increasing subsequence (adapted from Programming Exercise 22.2) Write a program MaxlncreasingSubseq.java that prompts the user to enter a string and displays a maximum length increasing subsequence of characters. Here are four sample runs Enter a string: zebras ers Enter a string: Welcome Welo Enter a string: mmmoooooovwwvee mov Enter a string: abqrstcxyzdefghij abcdefghij You must use dynamic programming, as discussed below and in the DynamicProgramming - HW2.ppt notes on Canvas, and your algorithm must run in O(nA2) time, where n is the length of the input string What is dynamic programming? Dynamic programming is a technique that works well when there is a recursive solution to a problem and the recursive subcases overlap. By "overlap" we mean that many of the individual subcases get used multiple times. In dynamic programming, we store solutions to the subcases so that they do not need to be recomputed. This approach can be much faster than a simple straight-forward recursion Let's consider the maximum increasing subsequence problem. Let scorej] be the length of the longest increasing subsequence that ends with the j-th character in the string. In the "Welcome" example, score would have the values 1 2 3 2 4 4 3 A suitable recurrence relation for computing score would be score[i] 1+ max(score吣j < i, charAt(j) < charAt(i)} Here charAt(i) returns the character at position i in the string. Clearly, if the set inside the above curly braces is empty, then score[i should be 1. This forms the base case of the recursion. Base your solution on the above recurrence relation. See the pseudocode in the DynamicProgramming HW2.ppt.

I really would appreciate some help with this assignment and include comments please as I am in this for learning.

Answer 1

//java program

import java.util.Scanner;
public class MaxIncreasingSubseq {
   public static void main(String args[]) {
       Scanner in = new Scanner (System.in);
       String string;
       System.out.print("Enter string : ");
       string = in.nextLine();
      
       printLIS(string);
       in.close();
      
   }
   public static void printLIS(String s) {
       int length = s.length();
       int DP[] = new int [length];
       int prev[] = new int [length];
       for(int i=0;i<length;i++)DP[i]=1;
       prev[0] = -1;
       int max,maxvalue;
       for(int i=1;i<length;i++) {
           max=0;maxvalue=0;
           for(int j=i-1;j>=0;j--) {
               if(s.charAt(i)>s.charAt(j)){
                   if(DP[j]>maxvalue) {
                       maxvalue=DP[j];
                   max=j;
                   }
               }
           }
           prev[i]=max;
           DP[i]=maxvalue+1;
       }
       max=0;
       for(int i=1;i<length;i++) {
           if(DP[i]>DP[max])max=i;
       }
      
       String str="";
       while(max!=-1) {
           str+=(s.charAt(max));
           max=prev[max];
       }
       for(int i=str.length()-1;i>=0;i--) {
           System.out.print(str.charAt(i));
       }
   }
}
//sample output

<terminated> MaxlncreasingSubseq Java Application] CProgram Files Javaljdk1.8.0 151\binljavaw.exe Enter string welcome belo