链条最大长度

Question

给你N对数字。在每一对中，第一个数字总是小于第二个数字。如果 b < c，一对 (c, d) 可以跟在另一对 (a, b) 之后。对链可以以这种方式形成。您的任务是完成函数 maxChainLen，其中 returns 一个整数，表示可以从给定的一组对中形成的最长链。

输入：
输入的第一行包含一个整数 T，表示测试用例的数量，然后是 T 个测试用例。然后是 T 个测试用例。输入的第一行包含一个整数 N，表示对的数量。下一行是 2*N space 个分隔值，表示 N 对。

输出：
对于每个测试用例，输出将是形成的最长链的长度。

约束条件：

1<=T<=100
1<=N<=100

示例（仅用于预期输出）：

输入

2
5
5  24 39 60 15 28 27 40 50 90
2
5 10 1 11

输出

3
1

说明

(i) 给定的对是 {{5, 24}, {39, 60}, {15, 28}, {27, 40}, {50, 90} }，最长的链可以是形成的长度为 3，链为 {{5, 24}, {27, 40}, {50, 90}}

(ii) 可能的最大链长度仅为一。

代码：

int maxChainLen(struct val p[],int n)
{
int dp[n];
dp[0]=1;
for(int i=1;i<=n;i++) {
    dp[i]=1;
   for(int j=0;j<i;j++) {
       if(p[j].second < p[i].first && dp[i]<dp[j]+1) {
           dp[i]=dp[j]+1;
       }
   }
}

int max=dp[0];
for(int i=0;i<n;i++) {
    if(dp[i]>max) {
        max=dp[i];
    }
}
return max;
}

算法：
与最长递增子序列相同，只是条件改变了((p[j].second < p[i].first)

但是在提交时，一些测试用例失败了；这个算法哪里出错了？

以下测试用例失败：

34
778 887 794 916 336 387 493 650 363 422 28 691 60 764 541 927 173 427 212 737 369 568 430 783 531 863 68 124 136 930 23 803 59 70 168 394 12 457 43 230 374 422 785 920 199 538 316 325 371 414 92 527 957 981 863 874 171 997 282 306 85 926 328 337 506 847 314 730

Its Correct output is:
8

And Your Code's output is:
4

Answer 1

你的代码逻辑错误。例如，当 i = 3, 时，您正在比较所有对 (0,1)、(0,2)、(0,3)，而您实际上只需要计算后续对。

此外，您使解决方案过于复杂。您可以在 O(n) 而不是 O(n^2) 中解决此问题。

您可以通过一次解析找到答案。在每次迭代中，如果它是一个链，你只需要增加电流dp[i]。

Answer 2

如果您将每对视为实线上的一个区间，那么挑战就是找到 Maximum Disjoint Set (MDS) of intervals. There's a fairly well known greedy algorithm 以在 O(nLgn) 中找到 MDS。

关键是首先按对的终点排序。大多数对该算法的解释都谈到从集合中删除重叠区间，但这并不是真正必要的。相反，您可以遍历排序列表，如果发现不相交的列表，则只增加当前对。

L = list of n pairs (a, b), a < b, sorted by b
count = 1
curr = 0
for i = 1 to n-1
  if L(i).a > L(curr).b
    count = count + 1
    curr = i

结果由count

给出

链条最大长度

Max length chain

algorithm

data-structures

longest-substring

array-algorithms