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
• 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.

Solution: 与longest ascending subsequence类似。先把点按x从小到大排序，再找y的最长递增序列

  public int largest(Point[] points) {
    if (points.length < 2) {
      return 0;
    }
    Arrays.sort(points, new Comparator<Point>() {
      public int compare(Point a, Point b) {
        if (a.x != b.x) {
          return a.x - b.x;
        }
        return a.y - b.y;
      }
    });
    int[] dp = new int[points.length];
    int max = 0;
    for (int i = 0; i < dp.length; i++) {
      dp[i] = 1;
      for (int j = 0; j < i; j++) {
        if (points[j].y < points[i].y) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
      max = Math.max(max, dp[i]);
    }
    //只有一个点时返回0
    if (max == 1) {
      return 0;
    }
    return max;
  }