バブルにスワップエレメントは、ソートバブルソートで

Question

問題ステートメント

に接続されている場合、私は、配列内の2つの要素を交換するたびに（ソートしながら）、すべての非接続要素の最大のサブセットを検索し、私は間のロープを結びますバブルソートが行われた後、他の要素と接続されていない配列内の最大セットのサイズを見つける必要があります。

例えば：{1、3、2}バブルソートの

第1の反復：

2及び3は、SO 3

{1,2,3}

と2を結ぶ入れ替え

2反復

この反復において、{1,2,3} ないスワップはそう他の要素との任意の要素を結ぶいけない

3反復

{1,2,3} この反復にはスワップはそうバブルソートだけ2,3の端部が互いに

結ばれた後に他の要素

で任意の要素を結ぶいけません

この例の答えは2です。なぜなら、要素のいずれも他の要素と結びついていない最大集合のサイズですからです。

可能なサブセット{1及び3をロープで縛られていないので}

可能な最大のセット（1及び2をロープで縛られていないため）{1,2}および{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です。

入力：

入力の最初の行は、Tが含まれている - 配列

の要素数 - なしテストケースの各テストケースの

最初の行は、N（1 < = N = 100000 <）を含みません各テストケースの

2行目は、配列

例のn個の要素を含む：

入力（例：から上記で説明）

出力：

私のアプローチ

それ最大のサブセットの長さは、最も長くなるサブシーケンスの長さになります。ここに私のコードがあります。間違った回答。助けてください！

#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

最初に、接続された各コンポーネントがインターバルであることを確認してください。

入力を2つの部分に分割した場合、最初の部分のすべての要素が2番目の部分のすべての要素以下である場合にのみ、部分にまたがるエッジは存在しません。

接続されたコンポーネントは、線形時間アルゴリズムを使用して識別できます。

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)