计算所有递增的子序列-yiteyi-C++库

我们得到一个数字数组（值在0到9之间）。任务是对数组中所有可能的子序列进行计数，以便在每个子序列中，每个数字都大于子序列中的前一个数字。

null

例如：

Input : arr[] = {1, 2, 3, 4}Output: 15There are total increasing subsequences{1}, {2}, {3}, {4}, {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}Input : arr[] = {4, 3, 6, 5}Output: 8Sub-sequences are {4}, {3}, {6}, {5}, {4,6}, {4,5}, {3,6}, {3,5}Input : arr[] = {3, 2, 4, 5, 4}Output : 14Sub-sequences are {3}, {2}, {4}, {3,4},{2,4}, {5}, {3,5}, {2,5}, {4,5}, {3,2,5}{3,4,5}, {4}, {3,4}, {2,4}

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

一个简单的解决方案是使用最长增长子序列（LIS）的动态规划解法问题喜欢利斯问题是，我们首先计算以每个索引结束的递增子序列的计数。最后，我们返回所有值的总和（在LCS问题中，我们返回所有值的最大值）。

// We count all increasing subsequences ending at every // index isubCount(i) = Count of increasing subsequences ending               at arr[i]. // Like LCS, this value can be recursively computedsubCount(i) = 1 + ∑ subCount(j)               where j is index of all elements              such that arr[j] < arr[i] and j < i.1 is added as every element itself is a subsequenceof size 1.// Finally we add all counts to get the result.Result = ∑ subCount(i)         where i varies from 0 to n-1.

插图：

For example, arr[] = {3, 2, 4, 5, 4}// There are no smaller elements on left of arr[0] // and arr[1]subCount(0) = 1subCount(1) = 1  // Note that arr[0] and arr[1] are smaller than arr[2]subCount(2) = 1 + subCount(0) + subCount(1)  = 3subCount(3) = 1 + subCount(0) + subCount(1) + subCount(2)             = 1 + 1 + 1 + 3            = 6  subCount(3) = 1 + subCount(0) + subCount(1)            = 1 + 1 + 1            = 3                             Result = subCount(0) + subCount(1) + subCount(2) + subCount(3)       = 1 + 1 + 3 + 6 + 3       = 14.

时间复杂度：O（n） ^2. ) 辅助空间：O（n）参考这用于实施。

方法2（高效）

上述解决方案没有利用给定数组中只有10个可能值的事实。我们可以使用数组count[]来使用这个事实，这样count[d]存储小于d的当前计数位数。

For example, arr[] = {3, 2, 4, 5, 4}// We create a count array and initialize it as 0.count[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}// Note that here value is used as index to store countscount[3] += 1 = 1  // i = 0, arr[0] = 3count[2] += 1 = 1  // i = 1, arr[0] = 2// Let us compute count for arr[2] which is 4count[4] += 1 + count[3] + count[2] += 1 + 1 + 1  = 3// Let us compute count for arr[3] which is 5count[5] += 1 + count[3] + count[2] + count[4]          += 1 + 1 + 1 + 3         = 6// Let us compute count for arr[4] which is 4count[4] += 1 + count[0] + count[1]         += 1 + 1 + 1         += 3         = 3 + 3         = 6            Note that count[] = {0, 0, 1, 1, 6, 6, 0, 0, 0, 0}                  Result = count[0] + count[1] + ... + count[9]       = 1 + 1 + 6 + 6 {count[2] = 1, count[3] = 1                        count[4] = 6, count[5] = 6}        = 14.

下面是上述想法的实现。

C++

                         // C++ program to count increasing subsequences                       
                         // in an array of digits.                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function To Count all the sub-sequences                       
                         // possible in which digit is greater than                       
                         // all previous digits arr[] is array of n                       
                         // digits                       
                         int                                     countSub(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // count[] array is used to store all sub-                       
                                                 // sequences possible using that digit                       
                                                 // count[] array covers all the digit                       
                                                 // from 0 to 9                       
                                                 int                                     count[10] = {0};                       
           
                                                 // scan each digit in arr[]                       
                                                 for                                     (                                     int                                     i=0; i<n; i++)                       
                                                 {                       
                                                 // count all possible sub-sequences by                       
                                                 // the digits less than arr[i] digit                       
                                                 for                                     (                                     int                                     j=arr[i]-1; j>=0; j--)                       
                                                 count[arr[i]] += count[j];                       
           
                                                 // store sum of all sub-sequences plus                       
                                                 // 1 in count[] array                       
                                                 count[arr[i]]++;                       
                                                 }                       
           
                                                 // now sum up the all sequences possible in                       
                                                 // count[] array                       
                                                 int                                     result = 0;                       
                                                 for                                     (                                     int                                     i=0; i<10; i++)                       
                                                 result += count[i];                       
           
                                                 return                                     result;                       
                         }                       
           
                         // Driver program to run the test case                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {3, 2, 4, 5, 4};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
           
                                                 cout << countSub(arr,n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count increasing                       
                         // subsequences in an array of digits.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
           
                                                 // Function To Count all the sub-sequences                       
                                                 // possible in which digit is greater than                       
                                                 // all previous digits arr[] is array of n                       
                                                 // digits                       
                                                 static                                     int                                     countSub(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 // count[] array is used to store all                       
                                                 // sub-sequences possible using that                       
                                                 // digit count[] array covers all                       
                                                 // the digit from 0 to 9                       
                                                 int                                     count[] =                                     new                                     int                                     [                                     10                                     ];                       
           
                                                 // scan each digit in arr[]                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 {                       
                                                 // count all possible sub-                       
                                                 // sequences by the digits                       
                                                 // less than arr[i] digit                       
                                                 for                                     (                                     int                                     j = arr[i] -                                     1                                     ; j >=                                     0                                     ; j--)                       
                                                 count[arr[i]] += count[j];                       
                                   
                                                 // store sum of all sub-sequences                       
                                                 // plus 1 in count[] array                       
                                                 count[arr[i]]++;                       
                                                 }                       
           
                                                 // now sum up the all sequences                       
                                                 // possible in count[] array                       
                                                 int                                     result =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i <                                     10                                     ; i++)                       
                                                 result += count[i];                       
           
                                                 return                                     result;                       
                                                 }                       
           
                                                 // Driver program to run the test case                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     3                                     ,                                     2                                     ,                                     4                                     ,                                     5                                     ,                                     4                                     };                       
                                                 int                                     n = arr.length;                       
           
                                                 System.out.println(countSub(arr,n));                       
                                                 }                       
                         }                       
                         // This code is contributed by Prerna Saini                       

Python3

                         # Python3 program to count increasing                       
                         # subsequences in an array of digits.                       
           
                         # Function To Count all the sub-                       
                         # sequences possible in which digit                       
                         # is greater than all previous digits                       
                         # arr[] is array of n digits                       
                         def                                     countSub(arr, n):                       
           
                                                 # count[] array is used to store all                       
                                                 # sub-sequences possible using that                       
                                                 # digit count[] array covers all the                       
                                                 # digit from 0 to 9                       
                                                 count                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (                                     10                                     )]                       
           
                                                 # scan each digit in arr[]                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                   
                                                 # count all possible sub-sequences by                       
                                                 # the digits less than arr[i] digit                       
                                                 for                                     j                                     in                                     range                                     (arr[i]                                     -                                     1                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ):                       
                                                 count[arr[i]]                                     +                                     =                                     count[j]                       
           
                                                 # store sum of all sub-sequences                       
                                                 # plus 1 in count[] array                       
                                                 count[arr[i]]                                     +                                     =                                     1                       
                                   
           
                                                 # Now sum up the all sequences                       
                                                 # possible in count[] array                       
                                                 result                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     10                                     ):                       
                                                 result                                     +                                     =                                     count[i]                       
           
                                                 return                                     result                       
           
                         # Driver Code                       
                         arr                                     =                                     [                                     3                                     ,                                     2                                     ,                                     4                                     ,                                     5                                     ,                                     4                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (countSub(arr, n))                       
           
                         # This code is contributed by Anant Agarwal.                       

C#

                         // C# program to count increasing                       
                         // subsequences in an array of digits.                       
                         using                                     System;                       
                         class                                     GFG {                       
           
                                                 // Function To Count all the sub-sequences                       
                                                 // possible in which digit is greater than                       
                                                 // all previous digits arr[] is array of n                       
                                                 // digits                       
                                                 static                                     int                                     countSub(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 // count[] array is used to store all                       
                                                 // sub-sequences possible using that                       
                                                 // digit count[] array covers all                       
                                                 // the digit from 0 to 9                       
                                                 int                                     []count =                                     new                                     int                                     [10];                       
           
                                                 // scan each digit in arr[]                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 {                       
                                                 // count all possible sub-                       
                                                 // sequences by the digits                       
                                                 // less than arr[i] digit                       
                                                 for                                     (                                     int                                     j = arr[i] - 1; j >= 0; j--)                       
                                                 count[arr[i]] += count[j];                       
                                   
                                                 // store sum of all sub-sequences                       
                                                 // plus 1 in count[] array                       
                                                 count[arr[i]]++;                       
                                                 }                       
           
                                                 // now sum up the all sequences                       
                                                 // possible in count[] array                       
                                                 int                                     result = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < 10; i++)                       
                                                 result += count[i];                       
           
                                                 return                                     result;                       
                                                 }                       
           
                                                 // Driver program                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr = {3, 2, 4, 5, 4};                       
                                                 int                                     n = arr.Length;                       
           
                                                 Console.WriteLine(countSub(arr,n));                       
                                                 }                       
                         }                       
                         // This code is contributed by Anant Agarwal.                       

Javascript

                         <script>                       
           
                         // Javascript program to count increasing                       
                         // subsequences in an array of digits.                       
           
                         // Function To Count all the sub-sequences                       
                         // possible in which digit is greater than                       
                         // all previous digits arr[] is array of n                       
                         // digits                       
                         function                                     countSub(arr, n)                       
                         {                       
                                   
                                                 // count[] array is used to store all sub-                       
                                                 // sequences possible using that digit                       
                                                 // count[] array covers all the digit                       
                                                 // from 0 to 9                       
                                                 let count =                                     new                                     Array(10).fill(0);                       
           
                                                 // Scan each digit in arr[]                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                   
                                                 // Count all possible sub-sequences by                       
                                                 // the digits less than arr[i] digit                       
                                                 for                                     (let j = arr[i] - 1; j >= 0; j--)                       
                                                 count[arr[i]] += count[j];                       
           
                                                 // Store sum of all sub-sequences plus                       
                                                 // 1 in count[] array                       
                                                 count[arr[i]]++;                       
                                                 }                       
           
                                                 // Now sum up the all sequences possible in                       
                                                 // count[] array                       
                                                 let result = 0;                       
                                                 for                                     (let i = 0; i < 10; i++)                       
                                                 result += count[i];                       
           
                                                 return                                     result;                       
                         }                       
           
                         // Driver code                       
                         let arr = [ 3, 2, 4, 5, 4 ];                       
                         let n = arr.length;                       
           
                         document.write(countSub(arr, n));                       
           
                         // This code is contributed by _saurabh_jaiswal                       
           
                         </script>                       

输出：

时间复杂度：O（n）注意，内部循环最多运行10次。辅助空间：O（1）注意count最多有10个元素。

本文由 沙申克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章