CODEWITHSUNDEEP
algorithm
Uoia
Uoia

Reputation: 11

Is this algorithm correct for finding the longest increasing sub-sequence?

I receive a non-sorted array and I need to find the longest increasing sub-sequence. According to Wikipedia the most efficient algorithm is O(nlogn) and this is O(n) so surely I'm doing something stupidly wrong

public static int[] longestAscending(int[] arr) {
        // {x /* starting index */, y /* ending index */};
        int[] max = {0, 0};
        int[] current = {0,1};

        for (int i=1; i<arr.length; i++) {
            if (arr[i-1] < arr[i]) {
                current[1]++;
                if (current[1] - current[0] > max[1] - max[0]) {
                    max[0] = current[0];
                    max[1] = current[1];
                }
            } else {
                current[0] = i;
                current[1] = i + 1;
            }
        }

        return max;
    }

Upvotes: 1

Views: 131

Answers (1)

orlp
orlp

Reputation: 117711

Your algorithm only detects contiguous subsequences, not subsequences with gaps. For example:

1 9 2 3

The longest increasing subsequence here is 1 2 3, which your algorithm doesn't find.

Upvotes: 1

Related Questions