给定一组数字，找到 L 长度 L 最长的 A. 算术的 P 前进( 美洲驼 )在里面。
null
例如：
set[] = {1, 7, 10, 15, 27, 29}output = 3The longest arithmetic progression is {1, 15, 29}set[] = {5, 10, 15, 20, 25, 30}output = 6The whole set is in AP
为了简单起见，我们假设给定的集合是排序的。我们总是可以添加一个预处理步骤，首先对集合进行排序，然后应用以下算法。
A. 简单解决方案 一个接一个地考虑每一对作为AP的前两个元素，并检查排序集合中的其余元素。要考虑所有的对作为第一个两个元素，我们需要运行一个O（n ^ 2）嵌套循环。在嵌套的循环中，我们需要第三个循环，它线性地寻找更多的元素 A. 算术的 P 前进( 美联社 ).这个过程需要O（n 3. )时间到了。 我们可以用O（n）来解决这个问题 2. )时间 使用动态规划 .为了了解DP解决方案，让我们首先讨论以下简单问题的解决方案。
给定一个排序集，找出算术级数中是否存在三个元素 请注意，如果AP中有3个或更多元素，则答案为真，否则为假。 为了找到这三个元素，我们首先将一个元素固定为中间元素，然后搜索其他两个元素（一个较小，一个较大）。我们从第二个元素开始，将每个元素固定为中间元素。为了使元素集[j]位于AP的中间，必须存在元素“set[i]”和“set[k]”，使得set[i]+set[k]=2*set[j]，其中0<=i
- 将i初始化为j-1，将k初始化为j+1
- 在i>=0和k<=n-1时执行以下操作
- 如果set[i]+set[k]等于2*set[j]，那么我们就完成了。
- 如果set[i]+set[k]>2*set[j]，则减量i（do i–）。
- 否则，如果set[i]+set[k]<2*set[j]，则增加k（do k++）。
下面是针对更简单问题的上述算法的实现。
C++
// The function returns true if there exist three // elements in AP Assumption: set[0..n-1] is sorted. // The code strictly implements the algorithm provided // in the reference. bool arithmeticThree(vector< int > set, int n) { // One by fix every element as middle element for ( int j = 1; j < n - 1; j++) { // Initialize i and k for the current j int i = j - 1, k = j + 1; // Find if there exist i and k that form AP // with j as middle element while (i >= 0 && k <= n-1) { if (set[i] + set[k] == 2 * set[j]) return true ; (set[i] + set[k] < 2 * set[j]) ? k++ : i--; } } return false ; } // This code is contributed by Samim Hossain Mondal. |
C
// The function returns true if there exist three elements in AP // Assumption: set[0..n-1] is sorted. // The code strictly implements the algorithm provided in the reference. bool arithmeticThree( int set[], int n) { // One by fix every element as middle element for ( int j=1; j<n-1; j++) { // Initialize i and k for the current j int i = j-1, k = j+1; // Find if there exist i and k that form AP // with j as middle element while (i >= 0 && k <= n-1) { if (set[i] + set[k] == 2*set[j]) return true ; (set[i] + set[k] < 2*set[j])? k++ : i--; } } return false ; } |
JAVA
// The function returns true if there exist three elements in AP // Assumption: set[0..n-1] is sorted. // The code strictly implements the algorithm provided in the reference. static boolean arithmeticThree( int set[], int n) { // One by fix every element as middle element for ( int j = 1 ; j < n - 1 ; j++) { // Initialize i and k for the current j int i = j - 1 , k = j + 1 ; // Find if there exist i and k that form AP // with j as middle element while (i >= 0 && k <= n- 1 ) { if (set[i] + set[k] == 2 *set[j]) return true ; (set[i] + set[k] < 2 *set[j])? k++ : i--; } } return false ; } // This code is contributed by gauravrajput1 |
Python3
# The function returns true if there exist three elements in AP # Assumption: set[0..n-1] is sorted. # The code strictly implements the algorithm provided in the reference. def arithematicThree(set_,n): # One by fix every element as middle element for j in range (n): # Initialize i and k for the current j i,k = j - 1 ,j + 1 # Find if there exist i and k that form AP # with j as middle element while i> - 1 and k<n: if set_[i] + set_[k] = = 2 * set_[j]: return True elif set_[i] + set_[k]< 2 * set_[j]: i - = 1 else : k + = 1 return False # This code is contributed by Kushagra Bansal |
C#
// The function returns true if there exist three elements in AP // Assumption: set[0..n-1] is sorted. // The code strictly implements the algorithm provided in the reference. static bool arithmeticThree( int [] set , int n) { // One by fix every element as middle element for ( int j = 1; j < n - 1; j++) { // Initialize i and k for the current j int i = j - 1, k = j + 1; // Find if there exist i and k that form AP // with j as middle element while (i >= 0 && k <= n-1) { if ( set [i] + set [k] == 2* set [j]) return true ; if ( set [i] + set [k] < 2* set [j]) k++; else i--; } } return false ; } // This code is contributed by gauravrajput1 |
Javascript
<script> // The function returns true if there exist three elements in AP // Assumption: set[0..n-1] is sorted. // The code strictly implements the algorithm provided in the reference. function arithmeticThree(set, n){ // One by fix every element as middle element for (let j=1; j<n-1; j++) { // Initialize i and k for the current j let i = j-1, k = j+1; // Find if there exist i and k that form AP // with j as middle element while (i >= 0 && k <= n-1) { if (set[i] + set[k] == 2*set[j]) return true ; (set[i] + set[k] < 2*set[j])? k++ : i--; } } return false ; } </script> |
看见 这 一个完整的运行程序。
如何为原始问题扩展上述解决方案？ 上面的函数返回一个布尔值。原始问题所需的输出为 L 长度 L 最长的 A. 算术的 P 前进( 美洲驼 )这是一个整数值。如果给定集合有两个或多个元素，那么LLAP的值至少为2（为什么？）。 其想法是创建一个二维表L[n][n]。该表中的条目L[i][j]存储LLAP，其中集合[i]和集合[j]是AP和j>i的前两个元素。该表的最后一列总是2（为什么——请参见L[i][j]的含义）。表格的其余部分从右下角到左上角填充。为了填充表格的其余部分，首先固定j（AP中的第二个元素）。搜索i和k以寻找固定的j。如果找到i和k，使得i，j，k形成AP，则L[i][j]的值设置为L[j][k]+1。请注意，当循环从右到左列遍历时，L[j][k]的值之前必须已填充。
下面是动态规划算法的实现。
C++
// C++ program to find Length of the Longest AP (llap) in a given sorted set. // The code strictly implements the algorithm provided in the reference. #include <iostream> using namespace std; // Returns length of the longest AP subset in a given set int lenghtOfLongestAP( int set[], int n) { if (n <= 2) return n; // Create a table and initialize all values as 2. The value of // L[i][j] stores LLAP with set[i] and set[j] as first two // elements of AP. Only valid entries are the entries where j>i int L[n][n]; int llap = 2; // Initialize the result // Fill entries in last column as 2. There will always be // two elements in AP with last number of set as second // element in AP for ( int i = 0; i < n; i++) L[i][n-1] = 2; // Consider every element as second element of AP for ( int j=n-2; j>=1; j--) { // Search for i and k for j int i = j-1, k = j+1; while (i >= 0 && k <= n-1) { if (set[i] + set[k] < 2*set[j]) k++; // Before changing i, set L[i][j] as 2 else if (set[i] + set[k] > 2*set[j]) { L[i][j] = 2, i--; } else { // Found i and k for j, LLAP with i and j as first two // elements is equal to LLAP with j and k as first two // elements plus 1. L[j][k] must have been filled // before as we run the loop from right side L[i][j] = L[j][k] + 1; // Update overall LLAP, if needed llap = max(llap, L[i][j]); // Change i and k to fill more L[i][j] values for // current j i--; k++; } } // If the loop was stopped due to k becoming more than // n-1, set the remaining entities in column j as 2 while (i >= 0) { L[i][j] = 2; i--; } } return llap; } /* Driver program to test above function*/ int main() { int set1[] = {1, 7, 10, 13, 14, 19}; int n1 = sizeof (set1)/ sizeof (set1[0]); cout << lenghtOfLongestAP(set1, n1) << endl; int set2[] = {1, 7, 10, 15, 27, 29}; int n2 = sizeof (set2)/ sizeof (set2[0]); cout << lenghtOfLongestAP(set2, n2) << endl; int set3[] = {2, 4, 6, 8, 10}; int n3 = sizeof (set3)/ sizeof (set3[0]); cout << lenghtOfLongestAP(set3, n3) << endl; return 0; } |
JAVA
// Java program to find Length of the // Longest AP (llap) in a given sorted set. // The code strictly implements the // algorithm provided in the reference. import java.io.*; class GFG { // Returns length of the longest // AP subset in a given set static int lenghtOfLongestAP( int set[], int n) { if (n <= 2 ) return n; // Create a table and initialize all // values as 2. The value ofL[i][j] stores // LLAP with set[i] and set[j] as first two // elements of AP. Only valid entries are // the entries where j>i int L[][] = new int [n][n]; // Initialize the result int llap = 2 ; // Fill entries in last column as 2. // There will always be two elements in // AP with last number of set as second // element in AP for ( int i = 0 ; i < n; i++) L[i][n - 1 ] = 2 ; // Consider every element as second element of AP for ( int j = n - 2 ; j >= 1 ; j--) { // Search for i and k for j int i = j - 1 , k = j + 1 ; while (i >= 0 && k <= n - 1 ) { if (set[i] + set[k] < 2 * set[j]) k++; // Before changing i, set L[i][j] as 2 else if (set[i] + set[k] > 2 * set[j]) { L[i][j] = 2 ; i--; } else { // Found i and k for j, LLAP with i and j as first two // elements is equal to LLAP with j and k as first two // elements plus 1. L[j][k] must have been filled // before as we run the loop from right side L[i][j] = L[j][k] + 1 ; // Update overall LLAP, if needed llap = Math.max(llap, L[i][j]); // Change i and k to fill // more L[i][j] values for current j i--; k++; } } // If the loop was stopped due // to k becoming more than // n-1, set the remaining // entities in column j as 2 while (i >= 0 ) { L[i][j] = 2 ; i--; } } return llap; } // Driver program public static void main (String[] args) { int set1[] = { 1 , 7 , 10 , 13 , 14 , 19 }; int n1 = set1.length; System.out.println ( lenghtOfLongestAP(set1, n1)); int set2[] = { 1 , 7 , 10 , 15 , 27 , 29 }; int n2 = set2.length; System.out.println(lenghtOfLongestAP(set2, n2)); int set3[] = { 2 , 4 , 6 , 8 , 10 }; int n3 = set3.length; System.out.println(lenghtOfLongestAP(set3, n3)) ; } } // This code is contributed by vt_m |
Python3
# Python 3 program to find Length of the # Longest AP (llap) in a given sorted set. # The code strictly implements the algorithm # provided in the reference # Returns length of the longest AP # subset in a given set def lenghtOfLongestAP( set , n): if (n < = 2 ): return n # Create a table and initialize all # values as 2. The value of L[i][j] # stores LLAP with set[i] and set[j] # as first two elements of AP. Only # valid entries are the entries where j>i L = [[ 0 for x in range (n)] for y in range (n)] llap = 2 # Initialize the result # Fill entries in last column as 2. # There will always be two elements # in AP with last number of set as # second element in AP for i in range (n): L[i][n - 1 ] = 2 # Consider every element as second # element of AP for j in range (n - 2 , 0 , - 1 ): # Search for i and k for j i = j - 1 k = j + 1 while (i > = 0 and k < = n - 1 ): if ( set [i] + set [k] < 2 * set [j]): k + = 1 # Before changing i, set L[i][j] as 2 elif ( set [i] + set [k] > 2 * set [j]): L[i][j] = 2 i - = 1 else : # Found i and k for j, LLAP with i and j # as first two elements are equal to LLAP # with j and k as first two elements plus 1. # L[j][k] must have been filled before as # we run the loop from right side L[i][j] = L[j][k] + 1 # Update overall LLAP, if needed llap = max (llap, L[i][j]) # Change i and k to fill more L[i][j] # values for current j i - = 1 k + = 1 # If the loop was stopped due to k # becoming more than n-1, set the # remaining entities in column j as 2 while (i > = 0 ): L[i][j] = 2 i - = 1 return llap # Driver Code if __name__ = = "__main__" : set1 = [ 1 , 7 , 10 , 13 , 14 , 19 ] n1 = len (set1) print (lenghtOfLongestAP(set1, n1)) set2 = [ 1 , 7 , 10 , 15 , 27 , 29 ] n2 = len (set2) print (lenghtOfLongestAP(set2, n2)) set3 = [ 2 , 4 , 6 , 8 , 10 ] n3 = len (set3) print (lenghtOfLongestAP(set3, n3)) # This code is contributed by ita_c |
C#
// C# program to find Length of the // Longest AP (llap) in a given sorted set. // The code strictly implements the // algorithm provided in the reference. using System; class GFG { // Returns length of the longest // AP subset in a given set static int lenghtOfLongestAP( int [] set , int n) { if (n <= 2) return n; // Create a table and initialize // all values as 2. The value of // L[i][j] stores LLAP with set[i] // and set[j] as first two elements // of AP. Only valid entries are // the entries where j>i int [,]L = new int [n, n]; // Initialize the result int llap = 2; // Fill entries in last column as 2. // There will always be two elements // in AP with last number of set as // second element in AP for ( int i = 0; i < n; i++) L[i, n - 1] = 2; // Consider every element as // second element of AP for ( int j = n - 2; j >= 1; j--) { // Search for i and k for j int i = j - 1 , k = j + 1; while (i >= 0 && k <= n - 1) { if ( set [i] + set [k] < 2 * set [j]) k++; // Before changing i, set L[i][j] as 2 else if ( set [i] + set [k] > 2 * set [j]) { L[i, j] = 2; i--; } else { // Found i and k for j, LLAP with // i and j as first two elements // is equal to LLAP with j and k // as first two elements plus 1. // L[j][k] must have been filled // before as we run the loop from // right side L[i, j] = L[j, k] + 1; // Update overall LLAP, if needed llap = Math.Max(llap, L[i, j]); // Change i and k to fill // more L[i][j] values for current j i--; k++; } } // If the loop was stopped due // to k becoming more than // n-1, set the remaining // entities in column j as 2 while (i >= 0) { L[i, j] = 2; i--; } } return llap; } // Driver Code static public void Main () { int []set1 = {1, 7, 10, 13, 14, 19}; int n1 = set1.Length; Console.WriteLine(lenghtOfLongestAP(set1, n1)); int []set2 = {1, 7, 10, 15, 27, 29}; int n2 = set2.Length; Console.WriteLine(lenghtOfLongestAP(set2, n2)); int []set3 = {2, 4, 6, 8, 10}; int n3 = set3.Length; Console.WriteLine(lenghtOfLongestAP(set3, n3)) ; } } // This code is contributed by Sach_Code |
PHP
<?php // PHP program to find Length of the // Longest AP (llap) in a given sorted set. // The code strictly implements the // algorithm provided in the reference. // Returns length of the longest AP // subset in a given set function lenghtOfLongestAP( $set , $n ) { if ( $n <= 2) return $n ; // Create a table and initialize all // values as 2. The value of L[i][j] // stores LLAP with set[i] and set[j] // as first two elements of AP. Only // valid entries are the entries where j>i $L [ $n ][ $n ] = array ( array ()); $llap = 2; // Initialize the result // Fill entries in last column as 2. // There will always be two elements // in AP with last number of set as // second element in AP for ( $i = 0; $i < $n ; $i ++) $L [ $i ][ $n - 1] = 2; // Consider every element as // second element of AP for ( $j = $n - 2; $j >= 1; $j --) { // Search for i and k for j $i = $j - 1; $k = $j + 1; while ( $i >= 0 && $k <= $n - 1) { if ( $set [ $i ] + $set [ $k ] < 2 * $set [ $j ]) $k ++; // Before changing i, set L[i][j] as 2 else if ( $set [ $i ] + $set [ $k ] > 2 * $set [ $j ]) { $L [ $i ][ $j ] = 2; $i --; } else { // Found i and k for j, LLAP with // i and j as first two elements // is equal to LLAP with j and k // as first two elements plus 1. // L[j][k] must have been filled // before as we run the loop from // right side $L [ $i ][ $j ] = $L [ $j ][ $k ] + 1; // Update overall LLAP, if needed $llap = max( $llap , $L [ $i ][ $j ]); // Change i and k to fill more // L[i][j] values for current j $i --; $k ++; } } // If the loop was stopped due to k // becoming more than n-1, set the // remaining entities in column j as 2 while ( $i >= 0) { $L [ $i ][ $j ] = 2; $i --; } } return $llap ; } // Driver Code $set1 = array (1, 7, 10, 13, 14, 19); $n1 = sizeof( $set1 ); echo lenghtOfLongestAP( $set1 , $n1 ), "" ; $set2 = array (1, 7, 10, 15, 27, 29); $n2 = sizeof( $set2 ); echo lenghtOfLongestAP( $set2 , $n2 ), "" ; $set3 = array (2, 4, 6, 8, 10); $n3 = sizeof( $set3 ); echo lenghtOfLongestAP( $set3 , $n3 ), "" ; // This code is contributed by Sach_Code ?> |
Javascript
<script> // Javascript program to find Length of the // Longest AP (llap) in a given sorted set. // The code strictly implements the // algorithm provided in the reference. // Returns length of the longest // AP subset in a given set function lenghtOfLongestAP(set,n) { if (n <= 2) return n; // Create a table and initialize all // values as 2. The value ofL[i][j] stores // LLAP with set[i] and set[j] as first two // elements of AP. Only valid entries are // the entries where j>i let L= new Array(n); for (let i=0;i<n;i++) { L[i]= new Array(n); } // Initialize the result let llap = 2; // Fill entries in last column as 2. // There will always be two elements in // AP with last number of set as second // element in AP for (let i = 0; i < n; i++) { L[i][n - 1] = 2; } // Consider every element as second element of AP for (let j = n - 2; j >= 1; j--) { // Search for i and k for j let i = j -1 , k = j + 1; while (i >= 0 && k <= n - 1) { if (set[i] + set[k] < 2 * set[j]) k++; // Before changing i, set L[i][j] as 2 else if (set[i] + set[k] > 2 * set[j]) { L[i][j] = 2; i--; } else { // Found i and k for j, LLAP with i and j as first two // elements is equal to LLAP with j and k as first two // elements plus 1. L[j][k] must have been filled // before as we run the loop from right side L[i][j] = L[j][k] + 1; // Update overall LLAP, if needed llap = Math.max(llap, L[i][j]); // Change i and k to fill // more L[i][j] values for current j i--; k++; } } // If the loop was stopped due // to k becoming more than // n-1, set the remaining // entities in column j as 2 while (i >= 0) { L[i][j] = 2; i--; } } return llap; } // Driver program let set1=[1, 7, 10, 13, 14, 19]; let n1 = set1.length; document.write( lenghtOfLongestAP(set1, n1)+ "<br>" ); let set2=[1, 7, 10, 15, 27, 29]; let n2 = set2.length; document.write( lenghtOfLongestAP(set2, n2)+ "<br>" ); let set3=[2, 4, 6, 8, 10]; let n3 = set3.length; document.write( lenghtOfLongestAP(set3, n3)+ "<br>" ); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
435
时间复杂性： O（n） 2. ) 辅助空间： O（n） 2. )
如何降低上述解决方案的空间复杂度？ 我们还可以将空间复杂度降低到 O（n） . 下面是具有空间复杂性的动态规划算法的实现 O（n） .
C++
// C++ program to find Length of the // Longest AP (llap) in a given sorted set. #include <bits/stdc++.h> using namespace std; // Returns length of the longest // AP subset in a given set int Solution(vector< int > A) { int ans = 2; int n = A.size(); if (n <= 2) return n; vector< int > llap(n, 2); sort(A.begin(), A.end()); for ( int j = n - 2; j >= 0; j--) { int i = j - 1; int k = j + 1; while (i >= 0 && k < n) { if (A[i] + A[k] == 2 * A[j]) { llap[j] = max(llap[k] + 1, llap[j]); ans = max(ans, llap[j]); i -= 1; k += 1; } else if (A[i] + A[k] < 2 * A[j]) k += 1; else i -= 1; } } return ans; } // Driver Code int main() { vector< int > a({ 9, 4, 7, 2, 10 }); cout << Solution(a) << endl; return 0; } // This code is contributed by ashutosh450 |
JAVA
// Java program to find Length of the // Longest AP (llap) in a given sorted set. import java.util.*; class GFG { // Returns length of the longest // AP subset in a given set static int Solution( int []A) { int ans = 2 ; int n = A.length; if (n <= 2 ) return n; int []llap = new int [n]; for ( int i = 0 ; i < n; i++) llap[i] = 2 ; Arrays.sort(A); for ( int j = n - 2 ; j >= 0 ; j--) { int i = j - 1 ; int k = j + 1 ; while (i >= 0 && k < n) { if (A[i] + A[k] == 2 * A[j]) { llap[j] = Math.max(llap[k] + 1 , llap[j]); ans = Math.max(ans, llap[j]); i -= 1 ; k += 1 ; } else if (A[i] + A[k] < 2 * A[j]) k += 1 ; else i -= 1 ; } } return ans; } // Driver Code public static void main(String[] args) { int []a = { 9 , 4 , 7 , 2 , 10 }; System.out.print(Solution(a) + "" ); } } // This code is contributed by Rajput-Ji |
Python3
# Python program to find Length # of the Longest AP (llap) in a given sorted set. # Returns length of the longest AP subset in a given set class Solution: def Solve( self , A): ans = 2 n = len (A) if n< = 2 : return n llap = [ 2 ] * n A.sort() for j in range (n - 2 , - 1 , - 1 ): i = j - 1 k = j + 1 while (i> = 0 and k<n): if A[i] + A[k] = = 2 * A[j]: llap[j] = max (llap[k] + 1 ,llap[j]) ans = max (ans, llap[j]) i - = 1 k + = 1 elif A[i] + A[k] < 2 * A[j]: k + = 1 else : i - = 1 return ans # Driver program to test above function obj = Solution() a = [ 9 , 4 , 7 , 2 , 10 ] print (obj.Solve(a)) |
C#
// C# program to find Length of the // longest AP (llap) in a given sorted set. using System; class GFG { // Returns length of the longest // AP subset in a given set static int Solution( int []A) { int ans = 2; int n = A.Length; if (n <= 2) return n; int []llap = new int [n]; for ( int i = 0; i < n; i++) llap[i] = 2; Array.Sort(A); for ( int j = n - 2; j >= 0; j--) { int i = j - 1; int k = j + 1; while (i >= 0 && k < n) { if (A[i] + A[k] == 2 * A[j]) { llap[j] = Math.Max(llap[k] + 1, llap[j]); ans = Math.Max(ans, llap[j]); i -= 1; k += 1; } else if (A[i] + A[k] < 2 * A[j]) k += 1; else i -= 1; } } return ans; } // Driver Code public static void Main(String[] args) { int []a = { 9, 4, 7, 2, 10 }; Console.Write(Solution(a) + "" ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript program to find Length of the // Longest AP (llap) in a given sorted set. // Returns length of the longest // AP subset in a given set function Solution(A) { let ans = 2; let n = A.length; if (n <= 2) { return n; } let llap = new Array(n); for (let i = 0; i < n; i++) { llap[i] = 2; } A.sort( function (a, b){ return a-b}); for (let j = n - 2; j >= 0; j--) { let i = j - 1; let k = j + 1; while (i >= 0 && k < n) { if (A[i] + A[k] == (2 * A[j])) { llap[j] = Math.max((llap[k] + 1), llap[j]); ans = Math.max(ans, llap[j]); i -= 1; k += 1; } else if (A[i] + A[k] < 2 * A[j]) k += 1; else i -= 1; } } return ans; } // Driver Code let a=[9, 4, 7, 2, 10 ]; document.write(Solution(a) + "<br>" ); // This code is contributed by rag2127 </script> |
输出：
3
时间复杂性： O（n） 2. ) 辅助空间： O（n） 上述解决方案由Umang Gupta提交
参考资料： http://www.cs.uiuc.edu/~jeffe/pubs/pdf/arith。pdf 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
