c - 使用回溯的子集

Question

我被要求使用回溯来解决以下问题: 它应该返回替换符号的最长差异子集的长度。 例如: 对于给定的序列 [11,6,7,8,9]，它返回 3。 因为它包含这个子集 [11,8,9] 和 [11,6,8] 。

*在本系列中 a:[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

您可以发送一个指针来保存递归函数中的最大值，每次到达 if(n==0) 时，您都必须检查 count_ones 是否大于 max，然后 max=count_ones