给定一个不同整数的数组，找出最长子数组的长度，该子数组包含可以连续排列的数字。 例如：
null
Input: arr[] = {10, 12, 11};Output: Length of the longest contiguous subarray is 3Input: arr[] = {14, 12, 11, 20};Output: Length of the longest contiguous subarray is 2Input: arr[] = {1, 56, 58, 57, 90, 92, 94, 93, 91, 45};Output: Length of the longest contiguous subarray is 5
我们强烈建议尽量减少浏览器，并先自己尝试。 值得注意的是，所有元素都是不同的。如果所有元素都是不同的，则当且仅当子数组中最大元素和最小元素之间的差值等于子数组的最后一个索引和第一个索引之间的差值时，子数组才具有连续元素。所以我们的想法是跟踪每个子阵列中的最小和最大元素。 以下是上述想法的实施。
C++
#include<iostream> using namespace std; // Utility functions to find minimum and maximum of // two elements int min( int x, int y) { return (x < y)? x : y; } int max( int x, int y) { return (x > y)? x : y; } // Returns length of the longest contiguous subarray int findLength( int arr[], int n) { int max_len = 1; // Initialize result for ( int i=0; i<n-1; i++) { // Initialize min and max for all subarrays starting with i int mn = arr[i], mx = arr[i]; // Consider all subarrays starting with i and ending with j for ( int j=i+1; j<n; j++) { // Update min and max in this subarray if needed mn = min(mn, arr[j]); mx = max(mx, arr[j]); // If current subarray has all contiguous elements if ((mx - mn) == j-i) max_len = max(max_len, mx-mn+1); } } return max_len; // Return result } // Driver program to test above function int main() { int arr[] = {1, 56, 58, 57, 90, 92, 94, 93, 91, 45}; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Length of the longest contiguous subarray is " << findLength(arr, n); return 0; } |
JAVA
class LargestSubArray2 { // Utility functions to find minimum and maximum of // two elements int min( int x, int y) { return (x < y) ? x : y; } int max( int x, int y) { return (x > y) ? x : y; } // Returns length of the longest contiguous subarray int findLength( int arr[], int n) { int max_len = 1 ; // Initialize result for ( int i = 0 ; i < n - 1 ; i++) { // Initialize min and max for all subarrays starting with i int mn = arr[i], mx = arr[i]; // Consider all subarrays starting with i and ending with j for ( int j = i + 1 ; j < n; j++) { // Update min and max in this subarray if needed mn = min(mn, arr[j]); mx = max(mx, arr[j]); // If current subarray has all contiguous elements if ((mx - mn) == j - i) max_len = max(max_len, mx - mn + 1 ); } } return max_len; // Return result } public static void main(String[] args) { LargestSubArray2 large = new LargestSubArray2(); int arr[] = { 1 , 56 , 58 , 57 , 90 , 92 , 94 , 93 , 91 , 45 }; int n = arr.length; System.out.println( "Length of the longest contiguous subarray is " + large.findLength(arr, n)); } } // This code has been contributed by Mayank Jaiswal |
Python3
# Python3 program to find length # of the longest subarray # Utility functions to find minimum # and maximum of two elements def min (x, y): return x if (x < y) else y def max (x, y): return x if (x > y) else y # Returns length of the longest # contiguous subarray def findLength(arr, n): # Initialize result max_len = 1 for i in range (n - 1 ): # Initialize min and max for # all subarrays starting with i mn = arr[i] mx = arr[i] # Consider all subarrays starting # with i and ending with j for j in range (i + 1 , n): # Update min and max in # this subarray if needed mn = min (mn, arr[j]) mx = max (mx, arr[j]) # If current subarray has # all contiguous elements if ((mx - mn) = = j - i): max_len = max (max_len, mx - mn + 1 ) return max_len # Driver Code arr = [ 1 , 56 , 58 , 57 , 90 , 92 , 94 , 93 , 91 , 45 ] n = len (arr) print ( "Length of the longest contiguous subarray is " , findLength(arr, n)) # This code is contributed by Anant Agarwal. |
C#
using System; class GFG { // Returns length of the longest // contiguous subarray static int findLength( int []arr, int n) { int max_len = 1; // Initialize result for ( int i = 0; i < n - 1; i++) { // Initialize min and max for all // subarrays starting with i int mn = arr[i], mx = arr[i]; // Consider all subarrays starting // with i and ending with j for ( int j = i + 1; j < n; j++) { // Update min and max in this // subarray if needed mn = Math.Min(mn, arr[j]); mx = Math.Max(mx, arr[j]); // If current subarray has all // contiguous elements if ((mx - mn) == j - i) max_len = Math.Max(max_len, mx - mn + 1); } } return max_len; // Return result } public static void Main() { int []arr = {1, 56, 58, 57, 90, 92, 94, 93, 91, 45}; int n = arr.Length; Console.WriteLine( "Length of the longest" + " contiguous subarray is " + findLength(arr, n)); } } // This code is contributed by Sam007. |
PHP
<?php // Utility functions to find minimum // and maximum of two elements function mins( $x , $y ) { if ( $x < $y ) return $x ; else return $y ; } function maxi( $a , $b ) { if ( $a > $b ) return $a ; else return $b ; } // Returns length of the longest // contiguous subarray function findLength(& $arr , $n ) { $max_len = 1; // Initialize result for ( $i = 0; $i < $n - 1; $i ++) { // Initialize min and max for all // subarrays starting with i $mn = $arr [ $i ]; $mx = $arr [ $i ]; // Consider all subarrays starting // with i and ending with j for ( $j = $i + 1; $j < $n ; $j ++) { // Update min and max in this // subarray if needed $mn = mins( $mn , $arr [ $j ]); $mx = maxi( $mx , $arr [ $j ]); // If current subarray has all // contiguous elements if (( $mx - $mn ) == $j - $i ) $max_len = maxi( $max_len , $mx - $mn + 1); } } return $max_len ; // Return result } // Driver Code $arr = array (1, 56, 58, 57, 90, 92, 94, 93, 91, 45); $n = sizeof( $arr ); echo ( "Length of the longest contiguous" . " subarray is " ); echo (findLength( $arr , $n )); // This code is contributed // by Shivi_Aggarwal. ?> |
Javascript
<script> // Utility functions to find minimum // and maximum of two elements function min( x, y) { return (x < y)? x : y; } function max( x, y) { return (x > y)? x : y; } // Returns length of the longest // contiguous subarray function findLength( arr, n) { let max_len = 1; // Initialize result for (let i=0; i<n-1; i++) { // Initialize min and max for all // subarrays starting with i let mn = arr[i], mx = arr[i]; // Consider all subarrays starting // with i and ending with j for (let j=i+1; j<n; j++) { // Update min and max in this // subarray if needed mn = min(mn, arr[j]); mx = max(mx, arr[j]); // If current subarray has all // contiguous elements if ((mx - mn) == j-i) max_len = Math.max(max_len, mx-mn+1); } } return max_len; // Return result } // driver code let arr = [1, 56, 58, 57, 90, 92, 94, 93, 91, 45]; let n = arr.length; document.write( "Length of the longest contiguous subarray is " + findLength(arr, n)); </script> |
输出：
Length of the longest contiguous subarray is 5
上述解的时间复杂度为O（n） 2. ).
我们将很快讨论子阵列中允许重复元素的问题的解决方案。 具有连续元素的最大子阵列的长度|集2 本文由 阿琼 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
