首页 > 代码库 > 二维的最长递增子序列问题。
二维的最长递增子序列问题。
有一些学生的成绩的数据，每个学生有sat和gpa成绩，如何找出一个最长的递增子序列，使得sat[1] < sat[2] < ... < sat[n] 且gpa[1] > gpa[2] > ... > gpa[n]
思路是做一次排序，对另一维使用传统的O(nlgn)的最长递增子序列的查找，只是找到了该学生可构成的最长递增子序列的长度d时，需要另外做一次判断，是否第一维和d-1长度的第一维是相等的。
package Solution;public class Solution{ private class score implements Comparable<Object> { public int sat; public int gpa; public int compareTo(Object obj) { score o = (score) obj; return gpa != o.gpa ? o.gpa - gpa : sat - o.sat; } public score(int _sat, int _gpa) { sat = _sat; gpa = _gpa; } } private score[] scores; private score[] scoreOfLength; private void input() { java.util.Scanner scanner = new java.util.Scanner(System.in); int N = scanner.nextInt(); scores = new score[N]; scoreOfLength = new score[N + 1]; for (int i = 0; i < N; ++i) { int sat = scanner.nextInt(); int gpa = scanner.nextInt(); scores[i] = new score(sat, gpa); } scanner.close(); } private int lower_bound(int x) { int p = 1; int q = scoreOfLength.length - 1; while(true) { int m = p + (q - p) / 2; if(scoreOfLength[m].sat >= x && scoreOfLength[m - 1].sat < x) { return m; } if(scoreOfLength[m].sat < x) { p = m + 1; } else { q = m - 1; } } } public int solve() { input(); java.util.Arrays.sort(scores); scoreOfLength[0] = new score(Integer.MIN_VALUE, -1); for(int i = 1; i < scoreOfLength.length; ++i) { scoreOfLength[i] = new score(Integer.MAX_VALUE, -1); } int ans = 0; for(int i = 0; i < scores.length; ++i) { int k = lower_bound(scores[i].sat); if(scores[i].gpa != scoreOfLength[k - 1].gpa) { scoreOfLength[k] = scores[i]; if(k > ans) { ans = k; } } } return ans; } public static void main(String[] args) { Solution s = new Solution(); System.out.println(s.solve()); }}
二维的最长递增子序列问题。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。