Java 中最长等差数列

2024 年 9 月 10 日 | 阅读 8 分钟

给定一个数组 arr[]，任务是找出数组中最长的算术递增序列的长度。

示例 1

输入: int arr[] = {30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140};

输出 12

解释: 数字序列 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140 构成算术递增序列，公差为 10，序列中总共有 12 个数字。

示例 2

输入: int arr[] = {15, 7, 20, 9, 14, 15, 25, 30, 90, 100, 35, 40};

输出 6

解释: 数字序列 15, 20, 25, 30, 35, 40 构成算术递增序列，公差为 5，序列中总共有 6 个数字。

让我们讨论解决这个问题的各种方法。

朴素方法

最简单或朴素的方法是逐一考虑每对元素，并将该对的元素视为算术递增序列的第一个（假设前两个元素是：a1 和 a2）。使用前两个元素，我们可以得到公差（a2 - a1）。使用这个公差，我们可以得到算术递增序列的后续元素。在查找后续元素的同时，我们还可以记录该算术递增序列的元素计数（countEle）。我们将为每对查找此计数（countEle），然后进行比较以找到最长的算术递增序列。请看以下程序。

文件名: LongestArithmeticProgression.java

public class LongestArithmeticProgression
{
// a method for finding the larger number between i & j
public int findMaxNo(int i, int j)
{
int maxNo;
return maxNo = (i > j) ? i : j;
}

public int findLongestApSeq(int arr[], int size)
{

// two or less than two elements always form 
// the arithmetic progression
if(size <= 2)
{
return size;
}

int ans = -1;

// loop for picking the first element of the
// arithemtic progression
for(int i = 0; i < size - 2; i++)
{

// loop for picking the second element of the
// arithemtic progression
for(int j = i + 1; j < size - 1; j++)
{
// finding the common difference
int comDiff = arr[j] - arr[i];

// multiple is 2 becuase the third element
// is first element + 2 * common difference
int multiple = 2;

// the first two loops has fixed the 
// first two elements of the arithmetic progresssion
int countEle = 2;

// loop for picking the subsequent elements (3rd, 4th, 5th, ..., so on)
// of the arithmetic progression
for(int k = j + 1; k < size; k++)
{
if((arr[i] + multiple * comDiff) == arr[k])
{
// element found hence increment the count
countEle = countEle + 1;

// 4th element of an arithmetic progression
// is defined as: a[i] + 3 * common difference
multiple = multiple + 1;
}
}


ans = findMaxNo(ans, countEle);

}
}

return ans;
}
// main method
public static void main(String argvs[]) 
{
// creating an object of the class LongestArithmeticProgression
LongestArithmeticProgression obj = new LongestArithmeticProgression();

// input array
int inputArr[] = {30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140};

int size = inputArr.length;

int longestSeq = obj.findLongestApSeq(inputArr, size);

System.out.println("For the following array: ");
for(int k = 0; k < size; k++)
{
System.out.print(inputArr[k] + " ");
}
System.out.println("\n");
System.out.println("The length of the longest arithmetic progression sequence is: " + longestSeq);

int inputArr1[] = {15, 7, 20, 9, 14, 15, 25, 30, 90, 100, 35, 40};

size = inputArr1.length;

longestSeq = obj.findLongestApSeq(inputArr1, size);

System.out.println("\n");

System.out.println("For the following array: ");
for(int k = 0; k < size; k++)
{
System.out.print(inputArr1[k] + " ");
}
System.out.println("\n");
System.out.println("The length of the longest arithmetic progression sequence is: " + longestSeq);


}
}

输出

For the following array: 
30 40 50 60 70 80 90 100 110 120 130 140 

The length of the longest arithmetic progression sequence is: 12


For the following array: 
15 7 20 9 14 15 25 30 90 100 35 40 

The length of the longest arithmetic progression sequence is: 6

复杂度分析: 在上述程序中，嵌套了三个 for 循环。因此，该程序的时间复杂度为 O(n³)，其中 n 是输入数组中存在的元素总数。该程序空间复杂度是常数，即 O(1)。

由于程序 O(n³) 的时间复杂度太高，需要通过一些优化来降低时间复杂度。以下方法展示了这一点。

动态规划方法

文件名: LongestArithmeticProgression1.java

// import statement for the HashMap
import java.util.HashMap;

public class LongestArithmetic1
{
// a method for finding the larger number between i & j
public int findMaxNo(int i, int j)
{
int maxNo;
return maxNo = (i > j) ? i : j;
}
public int findLongestApSeq(int arr[], int size)
{
// two or less than two elements always form 
// the arithmetic progression
if(size <= 2)
{
return size;
}
// creating a 2-d array whose row and column both
// are equal to the size of the input array
// Here, dp[i][j] means an arithmetic progression
// whose last two elements are arr[i] and arr[j], where i < j
int dp[][] = new int[size][size];
// using the hash map we have reduced the nesting of loop from 3 degree to
// 2 degree
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int ans = 0;
// loop for picking the second last element of the 
// arithmetic progression
for(int i = 0; i < size; i++)
{
// loop for picking the last element of the 
// arithemetic progression
for(int j = i + 1; j < size; j++)
{
// any two elements can be the  
// part of the arithmetic progression
dp[i][j] = 2;
// for an AP consisiting of three elements
// reqEle is the first element
// arr[i] is the second and arr[j] is the third element
int reqEle = 2 * arr[i] - arr[j];

if(hm.containsKey(reqEle))
{
// retrieving the index of the reqEle
int idx = hm.get(reqEle);
dp[i][j] = findMaxNo(dp[i][j], dp[idx][i] + 1);
ans = findMaxNo(ans, dp[i][j]);
}
}
// putting the arr[i] and its index i
// in the hashmap so that it is used later 
hm.put(arr[i], i);
}
return ans;
}
// main method
public static void main(String argvs[]) 
{
// creating an object of the class LongestArithmetic1
LongestArithmetic1 obj = new LongestArithmetic1();

// input array
int inputArr[] = {30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140};

int size = inputArr.length;

int longestSeq = obj.findLongestApSeq(inputArr, size);

System.out.println("For the following array: ");
for(int k = 0; k < size; k++)
{
System.out.print(inputArr[k] + " ");
}
System.out.println("\n");
System.out.println("The length of the longest arithmetic progression sequence is: " + longestSeq);

int inputArr1[] = {15, 7, 20, 9, 14, 15, 25, 30, 90, 100, 35, 40};

size = inputArr1.length;

longestSeq = obj.findLongestApSeq(inputArr1, size);
System.out.println("\n");
System.out.println("For the following array: ");
for(int k = 0; k < size; k++)
{
System.out.print(inputArr1[k] + " ");
}
System.out.println("\n");
System.out.println("The length of the longest arithmetic progression sequence is: " + longestSeq);
}
}

输出

For the following array: 
30 40 50 60 70 80 90 100 110 120 130 140 

The length of the longest arithmetic progression sequence is: 12

For the following array: 
15 7 20 9 14 15 25 30 90 100 35 40 

The length of the longest arithmetic progression sequence is: 6

复杂度分析: 在上述程序中，嵌套了两个 for 循环。因此，该程序的时间复杂度为 O(n²)，其中 n 是输入数组中存在的元素总数。我们还使用了二维数组，使得程序的空间复杂度为 O(n²)。

甚至，我们可以进行更多的优化来减少空间复杂度。以下方法展示了这一点。

使用双指针方法

在此方法中，我们将固定算术递增序列的中间元素，并尝试找出该序列的前一个和后一个元素。这将通过两个指针来完成。但是，在此之前，我们还需要对数组进行排序。因为如果给定的数组未排序，双指针方法将不起作用。

文件名: LongestArithmeticProgression2.java

// import statement for the Arrays
import java.util.Arrays;

public class LongestArithmetic2
{

public int findLongestApSeq(int arr[], int size)
{

// two or less than two elements always form 
// the arithmetic progression
if(size <= 2)
{
return size;
}

int ans = -1;
int dp[] = new int[size];


for(int j = 0; j < size; j++)
{
dp[j] = 2;
}

Arrays.sort(arr);
// loop for picking the middle element 
for (int i = size - 2; i >= 0; i--)
{
// two pointer approach
// j for the previous elements
// k for the next elements
int j = i - 1;
int k = i + 1;
while (j >= 0 && k < size)
{

if (arr[j] + arr[k] == 2 * arr[i])
{
dp[i] = Math.max(dp[k] + 1, dp[i]);
ans = Math.max(ans, dp[i]);
j = j - 1;
k = k + 1;
}

// if the sum is less than the twice of the middle 
// element increase the value by incremeting the 
//  k pointer
else if (arr[j] + arr[k] < 2 * arr[i])
{
k = k + 1;
}

// if the value is more than the twice of the middle 
// element decrease the value by decrementing the j pointer
else
{
j = j - 1;
}
}

}

return ans;
}
// main method
public static void main(String argvs[]) 
{
// creating an object of the class LongestArithmetic2
LongestArithmetic2 obj = new LongestArithmetic2();

// input array
int inputArr[] = {30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140};

int size = inputArr.length;

int longestSeq = obj.findLongestApSeq(inputArr, size);

System.out.println("For the following array: ");
for(int k = 0; k < size; k++)
{
System.out.print(inputArr[k] + " ");
}
System.out.println("\n");
System.out.println("The length of the longest arithmetic progression sequence is: " + longestSeq);

int inputArr1[] = {15, 7, 20, 9, 14, 15, 25, 30, 90, 100, 35, 40};

size = inputArr1.length;

longestSeq = obj.findLongestApSeq(inputArr1, size);

System.out.println("\n");

System.out.println("For the following array: ");
for(int k = 0; k < size; k++)
{
System.out.print(inputArr1[k] + " ");
}
System.out.println("\n");
System.out.println("The length of the longest arithmetic progression sequence is: " + longestSeq);


}
}

输出

For the following array: 
30 40 50 60 70 80 90 100 110 120 130 140 

The length of the longest arithmetic progression sequence is: 12


For the following array: 
15 7 20 9 14 15 25 30 90 100 35 40 

The length of the longest arithmetic progression sequence is: 6

复杂度分析: 时间复杂度与上面相同。但是，我们只使用了一维数组来完成任务。因此，我们将空间复杂度降低到 O(n)，其中 n 是输入数组中存在的元素总数。

下一主题Java中的套接字类型

Java 中最长等差数列

朴素方法

动态规划方法

使用双指针方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中最长等差数列

朴素方法

动态规划方法

使用双指针方法

相关帖子

Java 中的通用链表

How to Implement a Thread-Safe Resizable Array in Java

Compare Two ArrayList in Java

REPL in Java

NoClassDefFoundError in Java

Java protected keyword

Serialization and Deserialization of a Binary Tree in Java

Flutter vs Java

Java 中的悬空 else 问题

Java 中的 Border 布局管理器

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器