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

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)