查找C ++中最长双子序列的长度的程序

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个数字列表。我们必须找到最长的双子序列的长度。正如我们所知，如果严格地增加然后严格地减少，则该序列被称为二元序列。严格增加的顺序是双声的。或严格减少的顺序也是双音的。

因此，如果输入类似于nums = [0、8、4、12、2、10、6、14、1、9、5、13、11、7、15]，序列16的大小，则输出将是7。

为了解决这个问题，我们将遵循以下步骤-

  • 增加SubSeq：=给定数组大小的新数组，并用1填充

  • 对于初始化i：= 1，当i <size时，更新（将i增加1），执行-

    • 对于初始化j：= size-1，当j> i时，更新（将j减1），-

    • 对于初始化i：= 1，当i <size时，更新（将i增加1），执行-

    • reductionSubSeq [i]：= reductionSubSeq [j] + 1

    • 如果arr [i]> arr [j]，而reductionSubSeq [i] <reductionSubSeq [j] + 1，则-

    • 最大：=递增SubSeq [0] +递减SubSeq [0]-1

    • 最大值：=递增SubSeq [i] +递减SubSeq [i]-1

    • 如果递增SubSeq [i] +递减SubSeq [i]-1>最大值，则：

    • 最大回报

    • 如果arr [i]> arr [j]且递增的SubSeq [i] <递增的SubSeq [j] + 1，则-

    • * decreasingSubSeq：=给定数组大小的新数组，并用1填充

    • 递增SubSeq [i]：=增加SubSeq [j] + 1

    • 对于初始化j：= 0，当j <i时，更新（将j增加1），执行-

    • 对于初始化i：= size-2，当i> = 0时，更新（将i减1），执行-

    让我们看下面的实现以更好地理解-

    示例

    #include<iostream>
    using namespace std;
    int longBitonicSub( int arr[], int size ) {
       int *increasingSubSeq = new int[size];
       for (int i = 0; i < size; i++)
          increasingSubSeq[i] = 1;
       for (int i = 1; i < size; i++)
          for (int j = 0; j < i; j++)
             if (arr[i] > arr[j] && increasingSubSeq[i] <
             increasingSubSeq[j] + 1)
             increasingSubSeq[i] = increasingSubSeq[j] + 1;
       int *decreasingSubSeq = new int [size];
       for (int i = 0; i < size; i++)
          decreasingSubSeq[i] = 1;
       for (int i = size-2; i >= 0; i--)
          for (int j = size-1; j > i; j--)
             if (arr[i] > arr[j] && decreasingSubSeq[i] < decreasingSubSeq[j] + 1)
    decreasingSubSeq[i] = decreasingSubSeq[j] + 1;
       int max = increasingSubSeq[0] + decreasingSubSeq[0] - 1;
       for (int i = 1; i < size; i++)
          if (increasingSubSeq[i] + decreasingSubSeq[i] - 1 > max)
             max = increasingSubSeq[i] + decreasingSubSeq[i] - 1;
       return max;
    }
    int main() {
       int arr[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
       int n = 16;
       cout << longBitonicSub(arr, n);
    }

    输入值

    [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], 16

    输出结果

    7

    以上是 查找C ++中最长双子序列的长度的程序 的全部内容， 来源链接： utcz.com/z/317067.html

    回到顶部