1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
|
import java.util.Collections;
public class {
public int maxEnvelopes(int[][] envelopes) { if (envelopes.length == 0 || envelopes == null) return 0; int n = envelopes.length; int[] dp = new int[envelopes.length]; sort(envelopes); int max_count=0; int max_idx = 0; for (int i=1; i<envelopes.length; i++){ for (int j=0; j<i; j++){ if (envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){ dp[i] = Math.max(dp[i], dp[j] + 1); if (dp[i] > max_count){ max_count = dp[i]; max_idx = i; } } } } return dp[max_idx]+1;
} public static void sort(int[][] envelopes){ for (int i=1; i<envelopes.length; i++){ for (int j=0; j<i; j++){ if (envelopes[i][0]<envelopes[j][0]){ int[] temp = envelopes[i]; envelopes[i] = envelopes[j]; envelopes[j] = temp; } else if (envelopes[i][1]==envelopes[j][1]){ if (envelopes[i][1] < envelopes[j][1]){ int[] temp = envelopes[i]; envelopes[i] = envelopes[j]; envelopes[j] = temp; } } } }
} public static void main(String[] args){ int[][] test = new int[][]{{5,4},{6,4},{6,7},{2,3}}; sort(test); for (int[] a: test){ System.out.println(a[0] + " " + a[1]); } } }
|
近期评论