The maximum set

You are given an array $A$ of $N$ integer elements. A pair of elements $(i,j)$ is said to be an inversion if $A[i]>A[j]$ and $i<j$ for all $1\le i,j\le N$

Using this array $A$, you create an undirected graph $G$ of $N$ vertices. For each inversion pair $(i,j)$, there exists an edge between vertex $i$ and $j$.

Find the maximum size of set $S$ consisting of vertices from graph $G$ such that there exists an edge between every pair of vertices present in $S$.

Example:

Input:  n=4, a[] = { 4, 3, 2, 1 }
Output: 4

Approach

Java

import java.util.Arrays;

public class MaximumSet {

    public static void main(String[] args) {
        int n = 4;

        int[] a = { 4, 3, 2, 1 };

        int lisLength = LIS(a, n);

        System.out.println(lisLength);

    }

    static int findInd(int a[], int l, int r, int key) {
        while (r - l > 1) {
            int mid = l + (r - l) / 2;
            if (a[mid] >= key)
                r = mid;
            else
                l = mid;
        }

        return r;
    }

    static int LIS(int a[], int size) {
        Arrays.sort(a);
        int[] arr = new int[size];
        int len;
        arr[0] = a[0];
        len = 1;
        for (int i = 1; i < size; i++) {
            if (a[i] < arr[0])
                arr[0] = a[i];
            else if (a[i] > arr[len - 1])
                arr[len++] = a[i];
            else
                arr[findInd(arr, -1, len - 1, a[i])] = a[i];
        }

        return len;
    }

}