最大长度双音子阵|集1（O（n）时间和O（n）空间）-yiteyi-C++库

给定一个包含n个正整数的数组A[0…n-1]，如果存在一个i<=k<=j的k，则子数组A[i…j]是双音的，这样A[i]<=A[i+1]…=A[k+1]>=。。A[j–1]>=A[j]。编写一个函数，将数组作为参数，并返回最大长度的双音子数组的长度。解决方案的预期时间复杂度为O（n） 简单的例子 1) A[]={12,4,78,90,45,23}，最大长度的双音子阵是长度为5的{4,78,90,45,23}。 2) A[]={20,4,1,2,3,4,2,10}，最大长度的双音子阵是长度为5的{1,2,3,4,2}。 极端例子 1) A[]={10}，单个元素为双音，因此输出为1。 2) A[]={10,20,30,40}，整个数组本身是双音的，所以输出是4。 3) A[]={40,30,20,10}，整个数组本身是双音的，所以输出是4。

null

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

解决方案 让我们考虑数组{ 12, 4, 78，90, 45, 23 }来理解这个解决方案。 1）从左到右构造一个辅助阵列inc[]，使inc[i]包含以arr[i]结尾的非减缩子阵列的长度。对于A[]={12,4,78,90,45,23}，inc[]是{1,1,2,3,1,1} 2）从右到左构造另一个数组dec[]，使dec[i]包含从arr[i]开始的非递增子数组的长度。对于A[]={12,4,78,90,45,23}，dec[]是{2,1,1,3,2,1}。 3）一旦有了inc[]和dec[]数组，我们需要做的就是找到（inc[i]+dec[i]-1）的最大值。对于{12,4,78,90,45,23}，对于i=3，（inc[i]+dec[i]-1）的最大值是5。

C++

                         // C++ program to find length of                       
                         // the longest bitonic subarray                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     bitonic(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Length of increasing subarray                       
                                                 // ending at all indexes                       
                                                 int                                     inc[n];                       
                                   
                                                 // Length of decreasing subarray                       
                                                 // starting at all indexes                       
                                                 int                                     dec[n];                       
                                                 int                                     i, max;                       
           
                                                 // length of increasing sequence                       
                                                 // ending at first index is 1                       
                                                 inc[0] = 1;                       
           
                                                 // length of increasing sequence                       
                                                 // starting at first index is 1                       
                                                 dec[n-1] = 1;                       
           
                                                 // Step 1) Construct increasing sequence array                       
                                                 for                                     (i = 1; i < n; i++)                       
                                                 inc[i] = (arr[i] >= arr[i-1])? inc[i-1] + 1: 1;                       
           
                                                 // Step 2) Construct decreasing sequence array                       
                                                 for                                     (i = n-2; i >= 0; i--)                       
                                                 dec[i] = (arr[i] >= arr[i+1])? dec[i+1] + 1: 1;                       
           
                                                 // Step 3) Find the length of                       
                                                 // maximum length bitonic sequence                       
                                                 max = inc[0] + dec[0] - 1;                       
                                                 for                                     (i = 1; i < n; i++)                       
                                                 if                                     (inc[i] + dec[i] - 1 > max)                       
                                                 max = inc[i] + dec[i] - 1;                       
           
                                                 return                                     max;                       
                         }                       
           
                         /* Driver code */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {12, 4, 78, 90, 45, 23};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 cout <<                                     "nLength of max length Bitonic Subarray is "                                     << bitonic(arr, n);                       
                                                 return                                     0;                       
                         }                       
           
                         // This is code is contributed by rathbhupendra                       

C

                         // C program to find length of the longest bitonic subarray                       
                         #include<stdio.h>                       
                         #include<stdlib.h>                       
           
                         int                                     bitonic(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 int                                     inc[n];                                     // Length of increasing subarray ending at all indexes                       
                                                 int                                     dec[n];                                     // Length of decreasing subarray starting at all indexes                       
                                                 int                                     i, max;                       
           
                                                 // length of increasing sequence ending at first index is 1                       
                                                 inc[0] = 1;                       
           
                                                 // length of increasing sequence starting at first index is 1                       
                                                 dec[n-1] = 1;                       
           
                                                 // Step 1) Construct increasing sequence array                       
                                                 for                                     (i = 1; i < n; i++)                       
                                                 inc[i] = (arr[i] >= arr[i-1])? inc[i-1] + 1: 1;                       
           
                                                 // Step 2) Construct decreasing sequence array                       
                                                 for                                     (i = n-2; i >= 0; i--)                       
                                                 dec[i] = (arr[i] >= arr[i+1])? dec[i+1] + 1: 1;                       
           
                                                 // Step 3) Find the length of maximum length bitonic sequence                       
                                                 max = inc[0] + dec[0] - 1;                       
                                                 for                                     (i = 1; i < n; i++)                       
                                                 if                                     (inc[i] + dec[i] - 1 > max)                       
                                                 max = inc[i] + dec[i] - 1;                       
           
                                                 return                                     max;                       
                         }                       
           
                         /* Driver program to test above function */                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {12, 4, 78, 90, 45, 23};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 printf                                     (                                     "nLength of max length Bitonic Subarray is %d"                                     ,                       
                                                 bitonic(arr, n));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find length of the longest bitonic subarray                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     Bitonic                       
                         {                       
                                                 static                                     int                                     bitonic(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     [] inc =                                     new                                     int                                     [n];                                     // Length of increasing subarray ending                       
                                                 // at all indexes                       
                                                 int                                     [] dec =                                     new                                     int                                     [n];                                     // Length of decreasing subarray starting                       
                                                 // at all indexes                       
                                                 int                                     max;                       
           
                                                 // Length of increasing sequence ending at first index is 1                       
                                                 inc[                                     0                                     ] =                                     1                                     ;                       
           
                                                 // Length of increasing sequence starting at first index is 1                       
                                                 dec[n-                                     1                                     ] =                                     1                                     ;                       
           
                                                 // Step 1) Construct increasing sequence array                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 inc[i] = (arr[i] >= arr[i-                                     1                                     ])? inc[i-                                     1                                     ] +                                     1                                     :                                     1                                     ;                       
           
                                                 // Step 2) Construct decreasing sequence array                       
                                                 for                                     (                                     int                                     i = n-                                     2                                     ; i >=                                     0                                     ; i--)                       
                                                 dec[i] = (arr[i] >= arr[i+                                     1                                     ])? dec[i+                                     1                                     ] +                                     1                                     :                                     1                                     ;                       
           
                                                 // Step 3) Find the length of maximum length bitonic sequence                       
                                                 max = inc[                                     0                                     ] + dec[                                     0                                     ] -                                     1                                     ;                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i < n; i++)                       
                                                 if                                     (inc[i] + dec[i] -                                     1                                     > max)                       
                                                 max = inc[i] + dec[i] -                                     1                                     ;                       
           
                                                 return                                     max;                       
                                                 }                       
           
                                                 /*Driver function to check for above function*/                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     12                                     ,                                     4                                     ,                                     78                                     ,                                     90                                     ,                                     45                                     ,                                     23                                     };                       
                                                 int                                     n = arr.length;                       
                                                 System.out.println(                                     "Length of max length Bitnoic Subarray is "                       
                                                 + bitonic(arr, n));                       
                                                 }                       
                         }                       
                         /* This code is contributed by Devesh Agrawal */                       

Python3

                         # Python program to find length of the longest bitonic subarray                       
           
                         def                                     bitonic(arr, n):                       
                                   
                                                 # Length of increasing subarray ending at all indexes                       
                                                 inc                                     =                                     [                                     None                                     ]                                     *                                     n                       
                                   
                                                 # Length of decreasing subarray starting at all indexes                       
                                                 dec                                     =                                     [                                     None                                     ]                                     *                                     n                       
                                   
                                                 # length of increasing sequence ending at first index is 1                       
                                                 inc[                                     0                                     ]                                     =                                     1                       
                                   
                                                 # length of increasing sequence starting at first index is 1                       
                                                 dec[n                                     -                                     1                                     ]                                     =                                     1                       
           
                                                 # Step 1) Construct increasing sequence array                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 if                                     arr[i] >                                     =                                     arr[i                                     -                                     1                                     ]:                       
                                                 inc[i]                                     =                                     inc[i                                     -                                     1                                     ]                                     +                                     1                       
                                                 else                                     :                       
                                                 inc[i]                                     =                                     1                       
           
                                                 # Step 2) Construct decreasing sequence array                       
                                                 for                                     i                                     in                                     range                                     (n                                     -                                     2                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ):                       
                                                 if                                     arr[i] >                                     =                                     arr[i                                     -                                     1                                     ]:                       
                                                 dec[i]                                     =                                     inc[i                                     -                                     1                                     ]                                     +                                     1                       
                                                 else                                     :                       
                                                 dec[i]                                     =                                     1                       
           
                                                 # Step 3) Find the length of maximum length bitonic sequence                       
                                                 max                                     =                                     inc[                                     0                                     ]                                     +                                     dec[                                     0                                     ]                                     -                                     1                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 if                                     inc[i]                                     +                                     dec[i]                                     -                                     1                                     >                                     max                                     :                       
                                                 max                                     =                                     inc[i]                                     +                                     dec[i]                                     -                                     1                       
           
                                                 return                                     max                       
           
                         # Driver program to test above function                       
           
                         arr                                     =                                     [                                     12                                     ,                                     4                                     ,                                     78                                     ,                                     90                                     ,                                     45                                     ,                                     23                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (                                     "nLength of max length Bitonic Subarray is "                                     ,bitonic(arr, n))                       

C#

                         // C# program to find length of the                       
                         // longest bitonic subarray                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                                 static                                     int                                     bitonic(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 // Length of increasing subarray ending                       
                                                 // at all indexes                       
                                                 int                                     [] inc =                                     new                                     int                                     [n];                       
                                   
                                                 // Length of decreasing subarray starting                       
                                                 // at all indexes                       
                                                 int                                     [] dec =                                     new                                     int                                     [n];                       
                                   
                                                 int                                     max;                       
           
                                                 // Length of increasing sequence                       
                                                 // ending at first index is 1                       
                                                 inc[0] = 1;                       
           
                                                 // Length of increasing sequence                       
                                                 // starting at first index is 1                       
                                                 dec[n - 1] = 1;                       
           
                                                 // Step 1) Construct increasing sequence array                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 inc[i] = (arr[i] >= arr[i - 1]) ?                       
                                                 inc[i - 1] + 1: 1;                       
           
                                                 // Step 2) Construct decreasing sequence array                       
                                                 for                                     (                                     int                                     i = n - 2; i >= 0; i--)                       
                                                 dec[i] = (arr[i] >= arr[i + 1]) ?                       
                                                 dec[i + 1] + 1: 1;                       
           
                                                 // Step 3) Find the length of maximum                       
                                                 // length bitonic sequence                       
                                                 max = inc[0] + dec[0] - 1;                       
                                                 for                                     (                                     int                                     i = 1; i < n; i++)                       
                                                 if                                     (inc[i] + dec[i] - 1 > max)                       
                                                 max = inc[i] + dec[i] - 1;                       
           
                                                 return                                     max;                       
                                                 }                       
           
                                                 // Driver function                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     []arr = {12, 4, 78, 90, 45, 23};                       
                                                 int                                     n = arr.Length;                       
                                                 Console.Write(                                     "Length of max length Bitonic Subarray is "                       
                                                 + bitonic(arr, n));                       
                                                 }                       
                         }                       
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP program to find length of                       
                         // the longest bitonic subarray                       
           
                         function                                     bitonic(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 $i                                     ;                                     $max                                     ;                       
                                                 // length of increasing sequence                       
                                                 // ending at first index is 1                       
                                                 $inc                                     [0] = 1;                       
           
                                                 // length of increasing sequence                       
                                                 // starting at first index is 1                       
                                                 $dec                                     [                                     $n                                     - 1] = 1;                       
           
                                                 // Step 1) Construct increasing                       
                                                 // sequence array                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $inc                                     [                                     $i                                     ] = (                                     $arr                                     [                                     $i                                     ] >=                                     $arr                                     [                                     $i                                     - 1]) ?                       
                                                 $inc                                     [                                     $i                                     - 1] + 1: 1;                       
           
                                                 // Step 2) Construct decreasing                       
                                                 // sequence array                       
                                                 for                                     (                                     $i                                     =                                     $n                                     - 2;                                     $i                                     >= 0;                                     $i                                     --)                       
                                                 $dec                                     [                                     $i                                     ] = (                                     $arr                                     [                                     $i                                     ] >=                                     $arr                                     [                                     $i                                     + 1]) ?                       
                                                 $dec                                     [                                     $i                                     + 1] + 1: 1;                       
           
                                                 // Step 3) Find the length of                       
                                                 // maximum length bitonic sequence                       
                                                 $max                                     =                                     $inc                                     [0] +                                     $dec                                     [0] - 1;                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 if                                     (                                     $inc                                     [                                     $i                                     ] +                                     $dec                                     [                                     $i                                     ] - 1 >                                     $max                                     )                       
                                                 $max                                     =                                     $inc                                     [                                     $i                                     ] +                                     $dec                                     [                                     $i                                     ] - 1;                       
           
                                                 return                                     $max                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (12, 4, 78, 90, 45, 23);                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         echo                                     "Length of max length Bitonic "                                     .                       
                                                 "Subarray is "                                     , bitonic(                                     $arr                                     ,                                     $n                                     );                       
                                   
                         // This code is contributed by aj_36                       
                         ?>                       

Javascript

                         <script>                       
           
                                                 // Javascript program to find length of the                       
                                                 // longest bitonic subarray                       
                                   
                                                 function                                     bitonic(arr, n)                       
                                                 {                       
                                                 // Length of increasing subarray ending                       
                                                 // at all indexes                       
                                                 let inc =                                     new                                     Array(n);                       
                                   
                                                 // Length of decreasing subarray starting                       
                                                 // at all indexes                       
                                                 let dec =                                     new                                     Array(n);                       
                                   
                                                 let max;                       
                                   
                                                 // Length of increasing sequence                       
                                                 // ending at first index is 1                       
                                                 inc[0] = 1;                       
                                   
                                                 // Length of increasing sequence                       
                                                 // starting at first index is 1                       
                                                 dec[n - 1] = 1;                       
                                   
                                                 // Step 1) Construct increasing sequence array                       
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 inc[i] = (arr[i] >= arr[i - 1]) ? inc[i - 1] + 1: 1;                       
                                   
                                                 // Step 2) Construct decreasing sequence array                       
                                                 for                                     (let i = n - 2; i >= 0; i--)                       
                                                 dec[i] = (arr[i] >= arr[i + 1]) ? dec[i + 1] + 1: 1;                       
                                   
                                                 // Step 3) Find the length of maximum                       
                                                 // length bitonic sequence                       
                                                 max = inc[0] + dec[0] - 1;                       
                                                 for                                     (let i = 1; i < n; i++)                       
                                                 if                                     (inc[i] + dec[i] - 1 > max)                       
                                                 max = inc[i] + dec[i] - 1;                       
                                   
                                                 return                                     max;                       
                                                 }                       
                                   
                                                 let arr = [12, 4, 78, 90, 45, 23];                       
                                                 let n = arr.length;                       
                                                 document.write(                                     "Length of max length Bitonic Subarray is "                                     + bitonic(arr, n));                       
                                   
                         </script>                       

输出

nLength of max length Bitonic Subarray is 5

输出：

Length of max length Bitnoic Subarray is 5

时间复杂性： O（n） 辅助空间： O（n）

最大长度双音子阵|集2（O（n）时间和O（1）空间）作为练习，扩展上述实现以打印最长的双音子阵。上述实现仅返回此类子阵列的长度。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章