是LIS的变型题,如果遇到两维则先排序一维再对另一维动态规划
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.A pair (c, d) can follow another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. Find the longest chain
which can be formed from a given set of pairs.
Source:Amazon Interview | Set 2
For example, if the given pairs are {{5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90} }, then the longest chain that can be formed is of length 3, and the chain is {{5, 24}, {27, 40}, {50, 90}}
This problem is a variation of standardLongest Increasing Subsequenceproblem. Following is a simple two step process.
1) Sort given pairs in increasing order of first (or smaller) element.
2) Now run a modified LIS process where we compare the second element of already finalized LIS with the first element of new LIS being constructed.
The following code is a slight modification of method 2 ofthis post.
package DP;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
public class MaximumLengthChainOfPairs {
public static void main(String[] args) {
Pair p1 = new Pair(5, 24);
Pair p2 = new Pair(39, 60);
Pair p3 = new Pair(15, 28);
Pair p4 = new Pair(27, 40);
Pair p5 = new Pair(50, 90);
Pair[] A = {p1,p2,p3,p4,p5};
int n = A.length;
System.out.println(maxChainLength(A, n)); // {{5, 24}, {27, 40}, {50, 90}}
}
public static int maxChainLength(Pair[] A, int n){
Arrays.sort(A, new Comparator<Pair>() {
@Override
public int compare(Pair o1, Pair o2) {
return o1.a - o2.a;
}
});
// System.out.println(Arrays.toString(A));
int[] mcl = new int[n];
int max = 0;
/* Initialize MCL (max chain length) values for all indexes */
for(int i=0; i<n; i++){
mcl[i] = 1;
}
/* Compute optimized chain length values in bottom up manner */
for(int i=1; i<n; i++){
for(int j=0; j<i; j++){
if(A[j].b < A[i].a){ // 保证上升
mcl[i] = Math.max(mcl[i], mcl[j]+1);
}
}
}
// mcl[i] now stores the maximum chain length ending with pair i
/* Pick maximum of all MCL values */
for(int i=0; i<n; i++){
max = Math.max(max, mcl[i]);
}
return max;
}
public static class Pair{
int a;
int b;
public Pair(int a_, int b_){
a = a_;
b = b_;
}
@Override
public String toString() {
return "Pair [a=" + a + ", b=" + b + "]";
}
}
}
http://www.geeksforgeeks.org/dynamic-programming-set-20-maximum-length-chain-of-pairs/
分享到:
相关推荐
使用UM-DP12-25R和UM-DP20-25R(奥林巴斯,东京,日本)的EUS图像开发分类器。 根据我们的研究,分类器仅适用于... 服务器:更多信息,请参见文件夹“服务器”。 它可以在Linux上运行。 客户端:它在Windows上运行...
6300 维修手册 6300 维修手册 6300 维修手册
瑞士瑞诺伺服系统选型样本pdf,瑞士瑞诺伺服系统选型样本
3110c刷机包
小三本來下載速度就慢,有了它,就好了。小三(3110C)手機用的泡論壇軟件。
许继测量仪表DP20系列,moudbus规约详细描述。
诺基亚3110C强制刷机必备刷机包 3110C_RM-237_DP20_8.00_SW07.21.exe
NOKIA-5310系统刷5[1].81全教程 ...下载地址如下,然后是软件,5.81的新数据包必须要有,没有的可以下载:ftp://fox.365gsm.net/wangshao/5310_RM-303_DP20_3.00__sw-05.81.rar(把这个地址直接放讯雷里下载即可)
Shih3DP20, Shih, Meng-Li and Su, Shih-Yang and Kopf, Johannes and Huang, Jia-Bin, 3D Photography using Context-aware Layered Depth Inpainting, IEEE Conference on Computer Vision and Pattern ...