バックトラッキングを使用したサブセット

Question

バックトラッキングを使用して解決するように求められた質問は次のとおりです。 サインを置き換える差異のうち最も長いサブセットの長さを返すことになっています。 例：この系列[11,6,7,8,9]の場合、このサブセット[11,8,9]と[11,6,8]が含まれているため、 を返します。

*このシリーズでは、[11,8,9] a [1] -a [0] < 0とa [2] -a [1]> 0です。つまり、各近隣は変化する。 *

私はコーディングを終了しましたが、バックトラッキングを使用して最大長を返す方法がわかりません。

いずれのメモ/ヘルプも高く評価されます。

/* this function checks if we can add another number to the sequence 
    and still the differences between the numbers replace a sign.It's enough 
    to check the last two*/ 
int check_rec(int series[],int arr[],int n) 
{ int count=0,c=n; 
    int temp1=0,temp2=0; 
    while(c>=0 && count!=2) 
    { 
     if (arr[c]==1 && count==0) 
     { temp1=series[c]; 
      count++; 
     } 
     if (arr[c]==1 && count==1) 
     { temp1=series[c]; 
      count++; 
     } 
     c--; 
    } 
    if(count<2) return 1; 
    if(temp1>temp2 && series[n+1] < temp1) return 1; 
    if(temp1<temp2 && series[n+1]> temp1) return 1; 
    return 0; 
} 

int count_ones(int arr[],int n) 
{ int c; 
    for(int i=0;i<n;i++) 
    { 
     if(arr[i]) 
      c++; 
    } 
    return c; 
} 
    // 1 in the array helper indicates that the index has been chosen. 
    void max_crazy(int series[], int n,int helper[],int length,int max[]) 
{ 
    if(n==0) 
     { 
      int x=count_ones(helper,n); 
      if(x>max[0]) 
       max[0]=x; 
      } 
    for(int i=0;i<2;i++) 
    { 
     if(n!=length && i==1 && !check_rec(series,helper,length-n)) 
      continue; 

     helper[0]=i; 
     max_crazy(series,n-1,helper+1,length,max); 
    } 

} 

Answer 1

あなたが到達再帰関数のmaxを保存し、ポインタ、およびすべての時間を送ることができます（nは== 0）あなたは確認する必要があればcount_ones maxよりも大きいそして最大= count_ones

場合