-1

I need to return the number of LIS of the array.

Pseudocode example:

if the arr is
 int []arr = {2,4,90,-3,-2,-1,-10,-9,-8};
num of LIS is: 3
 2,4,90
 -3,-2,-1
 -10,-9,-8

example 2:

arr [] = {2,-3,4,90,-2,-1,-10,-9,-8};
num of LIS is: 4
2,4,90
-3,4,90
-3,-2,-1
-10,-9,-8

I have tried to do this:

int [] A = {2,4,90,-3,-2,-1,-10,-9,-8};
    int[] dp = new int[A.length];

    for (int i = 0; i < A.length; i++) {
        dp[i] = 1;

        for (int j = 0; j <= i - 1; j++) {
            if (A[j] < A[i]) {
                dp[i] = dp[i] + dp[j];
            }
        }
        System.out.println(dp[dp.length - 1] ) ;
    }
4pie0
  • 29,204
  • 9
  • 82
  • 118
agamoti
  • 13
  • 1
  • 2
  • 4
    what problem are you facing ? – Kakarot Feb 26 '14 at 15:51
  • You should try to find the min val and then assign it – Kakarot Feb 26 '14 at 15:52
  • You can probably brute force this in quadratic time. – Mark Jeronimus Feb 26 '14 at 15:54
  • @Zom-B You can find *all* of the complete increasing subsequences in linear time, since each starts after the end of the previous one. There's no need to "start back from the beginning" to find the next increasing subsequence, which is what would make it quadratic time. – Servy Feb 26 '14 at 15:57
  • Why is '2,4,90' a increasing subsequence of {2,-3,4,90,-2,-1,-10,-9,-8}? Surely is stopped increasing at -3? – Jack0x539 Feb 26 '14 at 16:17
  • 1
    StackOverflow is not a site for doing your homework for you. This isn't a question, this is a list of facts. – Eric Lippert Feb 26 '14 at 16:20

1 Answers1

1

In your code you just keep on adding to the dp[i] for all lookups in the inner for loop. Ideally you should find the maximum size of the subsequence for all positions (j < i) and then add that maximum Value to d[i]. Correct way is as follows : 

int maxSizeOfSubseq = 0;
for (int i = 0; i < A.length; i++) {
    dp[i] = 1;
    maxSizeOfSubseq = 0;
    for (int j = 0; j <= i - 1; j++) {
        if (A[j] < A[i] && dp[j] > maxSizeOfSubseq ) {
            maxSizeOfSubseq = dp[j];
        }
    }
    dp[i] = dp[i] + maxSizeOfSubseq ;
             System.out.println(dp[dp.length - 1] ) ;
}


// Now find the Max Size Of Subsequence amongst all computes subsequence lengths
maxSizeOfSubseq  = 0;
for(int count = 0 ; count < dp.length; ++count)
{
  if(dp[i] > maxSizeOfSubseq )
  {
  maxSizeOfSubseq  = dp[i]
  }
}

return maxSizeOfSubseq ;
Kakarot
  • 4,252
  • 2
  • 16
  • 18