LIS Question

[Mark Nibert]

I am working on a LIS program. I got it to give me the LIS value but I cannot figure out how to get it to print out the values that are in the LIS. I am looking for some help.

class LIS
{

  public static void main(String args[])
  {
    int ar[];
    int arSize;
    int L;
     String prntStr = "";
     ar = initAR();
     L = increasingSubsequence(ar);
     System.out.println(L);
  }



  public static int increasingSubsequence(int[]seq){
    int[]L=new int[seq.length];
    L[0]=1;
    for(int i=1;i<L.length;i++){
      int maxn=0;
      for(int j=0;j<i;j++){
        if(seq[j]<seq[i]&&L[j]>maxn){
          maxn=L[j];
        }
      }
      L[i]=maxn+1;
    }
    int maxi=0;
    for(int i=0;i<L.length;i++){
      if(L[i]>maxi){
        maxi=L[i];
      }
    }
    return(maxi);
  }

  public static int[] initAR(){
    int arSize = 9;
    int[] ar = new int[arSize];
    ar[0] = 11;
    ar[1] = 17;
    ar[2] = 5;
    ar[3] = 8;
    ar[4] = 6;
    ar[5] = 4;
    ar[6] = 7;
    ar[7] = 12;
    ar[8] = 3;

    return ar;
  }

}

[Ninad Kulkarni]

Hi Mark,
Would you tell me what is the meaning of LIS here?

[Mark Nibert]

I apologize, Longest Increasing Subsequence.

[Ralph Cook]

If LIS is some kind of standard abbreviation, I'm not familiar with it.

It appears that your code creates an array of integers, determines the largest value in that array, and prints out that value.

If you want to print out each value in the array, then iterate through the values much like you do when you're looking for the max

for (int i=0; i < ary.length; i++)
{
  System.out.println(ary[i]);
}

[Mark Nibert]

Yeah, I can do it for the original values but it is finding the Longest Increasing Subsequence and right now it gives me the count of 4 which is correct. I just cant figure out how to get it to print out the values that it finds the count for. In this example it would be 5 6 7 12

[Ralph Cook]

Well, read my last post. Try it out. Ask a specific question.

[Mark Nibert]

I need to figure out how to get it to print the numbers it is finding to calculate the LIS. I changed it below the print the original array. But when it calculates the hops (4 in this instance) I need to have it print the values that are included in that count.

class LIS
{

  public static void main(String args[])
  {
    int ar[];
    int arSize;
    int L;
     String prntStr = "";
     ar = initAR();
     L = increasingSubsequence(ar);
     System.out.println("\nLIS Count = "+L);
  }



  public static int increasingSubsequence(int[]seq){
    int[]L=new int[seq.length];
    L[0]=1;
    for(int i=1;i<L.length;i++){
      int maxn=0;
      for(int j=0;j<i;j++){
        if(seq[j]<seq[i]&&L[j]>maxn){
          maxn=L[j];
        }
      }
      L[i]=maxn+1;
    }
    int maxi=0;
    for(int i=0;i<L.length;i++){
      if(L[i]>maxi){
        maxi=L[i];
      }
    }
    return(maxi);
  }

  public static int[] initAR(){
    int arSize = 9;
    int[] ar = new int[arSize];
    ar[0] = 11;
    ar[1] = 17;
    ar[2] = 5;
    ar[3] = 8;
    ar[4] = 6;
    ar[5] = 4;
    ar[6] = 7;
    ar[7] = 12;
    ar[8] = 3;
    
    System.out.println("Original Array: ");
    for(int i = 0; i < arSize; i++)
    {
    	System.out.print(ar[i]+ " ");
    }
    return ar;
  }

}

[Ralph Cook]

I do not know if you are not understanding; it certainly appears to me that you are not making much of an effort here.

I've given you code that iterates through your list and writes out values from it. Is there some reason that you cannot adapt that to write out whatever you want at whatever point you want?

If so, please ask a specific question. At this point, especially, I urge you to show me what you have tried, what it does that you don't want it to do, and what you don't understand about it.

I'm afraid your tone and lack of specificity suggest you want me to do your programming for you, and that is not what either I or this forum is for.

rc

[Mark Nibert]

I am just not sure where to start. I need to figure out a way in the increasingsubsequence method to print out the values are being stored as members of the subsequence that is being counted. I am just extremely lost and my lack of programming expertise is leaving me not being able to be more specific. I think I need to create another array and figure out a way to store the variables but I am just not sure.

[Ralph Cook]

Try starting with pseudocode: it is procedural code with no syntax rules. All you are doing with it is writing down the steps a (hypothetical) computer would take to do what you want to do.

It helps separate what you know how to do from what you don't know -- you know you can assign variables, declare arrays, iterate through arrays, print out values, and call methods that do those things and optionally return values to you. Your pseudocode can use java statements for that or not, as you choose, make it easy on yourself. But try to create step-by-step pseudocode that does what you want, and then put that in a question. I'm guessing it will help you put a pseudocomment in the code that says something like "Here I want all my Xs to turn blue, but I don't know a statement for that", or whatever it is you're after.

Or you will figure out that, once you have the pseudocode written, you can translate it to Java, at least to give it a try.

Good luck

rc