找到所有的非连接的元件的最大子集，如果元素在冒泡排序连接

Question

问题描述

在冒泡排序，每当我交换阵列中的两个元件（而分选），我扎之间的绳索交换我需要找到数组中最大集合的大小，其中在完成冒泡排序之后，没有任何元素与任何其他元素相连接。

例如：{1,3，2}

冒泡排序的第一迭代：

2和3交换，以便配合2与3

{1，2,3}

第二迭代

{1,2,3} 没有在本次迭代中互换，所以不要配合任何元件与任何其它元件

第三迭代

{1,2,3} 在本次迭代中没有互换，所以不要气泡的端排序仅2和3连接在一起

之后与任何其他元件

扎任何元件

这个例子的答案是2，因为最大集的大小没有任何元素与任何其他元素绑定在一起。

可能的最大集合是{1,2}（因为1和2未用绳子绑）和{1,3} {因为1和3不与绳子绑}

可能子集这个数组是{1}，{2}，{3}，{1,2}，{1,3}，{3,2} {1,3,2}，{}

其中，有效的子集是{1}，{2}，{3}，{1,2}，{1,3}在这个有效的子集{1,2}和{1,3}是更大的子集。子集是2，所以答案是2。

输入：

输入的第一行包含笔 - 否的测试案例

每个测试用例的第一行包含N（1 < = N < = 100000） - 数组

中的元素数

每个测试用例的第二行包含阵列

示例的n个元素：

输入：（从上述的例子中）

输出：

我的方法

我t最大子集长度将是最长增加子序列的长度，这里是我的代码得到错误答案。请帮忙！

#include <iostream> 
using namespace std; 

int bs(int a[],int x,int lo,int hi) 
{ 
while(hi-lo>1) 
{ 
    int mid=(hi+lo)/2; 
    if(a[mid]>=x) 
    hi=mid; 
    else 
    lo=mid; 
} 
return hi; 
} 

int main() { 
int t; 
cin>>t; 
while(t--) 
{ 
    int n,m=1; 
    cin>>n; 
    int a[n+1]; 
    for(int i=0;i<n;i++) 
    cin>>a[i]; 
    int dp[n+1]; 
    for(int i=0;i<n;i++) 
    dp[i]=0; 
    dp[0]=a[0]; 
    for(int i=1;i<n;i++) 
    { 
     if(dp[0]>a[i]) 
     dp[0]=a[i]; 
     else if(a[i]>dp[m-1]) 
     dp[m++]=a[i]; 
     else 
     { 
      int x=bs(a,a[i],-1,m-1); 
      dp[x]=a[i]; 
     } 
    } 
    cout<<m<<endl; 
} 
return 0; 
} 

Answer 1

首先通过归纳法来观察，即每个连通分量是一个区间。

接下来观察到，给定输入分为两部分的情况，当且仅当第一部分中的每个元素小于或等于第二部分中的每个元素时，没有跨越部分的边。

可以使用线性时间算法来识别连接的组件。

def count(lst): 
    compmaxes = [] # holds the maximum of each connected component 
    for x in lst: 
     if not compmaxes or compmaxes[-1] <= x: 
      compmaxes.append(x) 
     else: 
      while len(compmaxes) > 1 and compmaxes[-2] > x: 
       del compmaxes[-2] 
    return len(compmaxes)