Given an array of 2D coordinates of points (all the coordinates are integers), find the largest number of points that can form a set such that any pair of points in the set can form a line with positive slope. Return the size of such a maximal set.

Assumptions

• The given array is not null and is not empty
• Note : if there does not even exist 2 points can form a line with positive slope, should return 0.

Examples

• <0, 0>, <1, 1>, <2, 3>, <3, 3>, the maximum set of points are {<0, 0>, <1, 1>, <2, 3>}, the size is 3.

public int largest(Point[] points) {

import java.util.Arrays;
import java.util.Comparator;

public class LongestSetofPositiveSlope {


    public int largest(Point[] points) {
        // Write your solution here.
        if (points == null) {
            return 0;
        }

        Arrays.sort(points, new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                if (o1.x < o2.x) {
                    return -1;
                } else if (o1.x > o2.x){
                    return 1;
                } else if (o1.y < o2.y) {
                    return -1;
                } else if (o1.y > o2.y) {
                    return 1;
                } else {
                    return 0;
                }
            }
        });

        // longest subsequence of y
        int[] dp = new int[points.length];
        int result = 0;
        for(int i = 0; i < points.length; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if (points[j].x < points[i].x && points[j].y < points[i].y) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                }
            }

            result = Math.max(result, dp[i]);
        }
        return result == 1 ? 0 : result;
    }
}