最大化给定数组中最长递增质数子序列的长度
给定大小为N的数组arr[]，任务是通过执行以下操作来找到最长递增质数子序列的长度。
-
如果
arr[i]已经是质数，则无需更新arr[i]。 -
将非质数
arr[i]更新为小于arr[i]的最接近质数。 -
将非质数
arr[i]更新为大于arr[i]的最接近质数。
示例：
输入：
arr[] = {8, 6, 9, 2, 5}输出：2
说明：
可能的数组的重排为：
{{7, 5, 2, 5}, {7, 7, 2, 5}, {11, 5, 2, 5}, {1, 7, 2, 5}}。因此，最长递增的质数子序列的长度为 2。
输入：
arr[] = {27, 38, 43, 68, 83, 12, 69, 12}输出：5
朴素的方法：最简单的方法是将给定数组的所有元素更新为最接近的较小质数或最接近的较大质数，然后生成给定数组的所有可能子序列排列并按升序打印由质数组成的最长子序列的长度。
时间复杂度：O(2 ^ N)。
辅助空间：O(n)。
高效方法：想法是使用动态规划方法来优化上述方法。 此问题是最长递增质数子序列（LIPS）问题的基本变体。 请按照以下步骤解决问题。
-
初始化二维数组，例如
dp[][]，大小为N * 2，其中通过选择小于索引i处的arr[i]的最接近质数，dp[i][0]存储最长增长质数子序列的长度。 通过选择大于或等于索引i处的arr[i]的最接近质数，dp[i][1]存储最长递增质数子序列的长度。 下面是递归关系：- 如果最接近
arr[j]的较小的质数小于最接近arr[i]的较小的质数：dp[i][0] = 1 + dp[j][0]。 - 如果最接近
arr[j]的较大或相等的质数小于最接近arr[i]的较大或相等的质数：dp[i][0] = max(dp[i][0], 1 + dp[j][1])。 - 如果最接近
arr[j]的较小的质数小于最接近arr[i]的较小的质数：dp[i][1] = 1 + dp[j][0]。 - 如果最接近
arr[j]的较大或相等的质数小于最接近arr[i]的较大或相等的质数：dp[i][1] = max(dp[i][1], 1 + dp[j][1])。
这里
j的值为0, 1, …, i - 1。 - 如果最接近
-
使用 Eratosthenes 筛子有效地计算质数。
-
遍历数组
arr[]，对于每个索引i，将arr[i]更新为最接近arr[i]的质数。 -
对于每个索引
i，最佳地找到以i结尾的最长递增质数子序列的长度。 -
最后，返回最长的质数子序列的长度。
下面是上述方法的实现：
Java
// Java Program to implement
// the above approach
import java.util.*;
public class Main {
// Stores the closest prime
// number for each array element
static TreeSet<Integer> set
= new TreeSet<>();
// Function to find the length of longest
// increasing prime subsequence
public static int LIPS(int arr[], int N)
{
// Base case
if (arr.length == 0)
return 0;
int dp[][] = new int[N + 1][2];
// Store the length of the longest
// increasing prime subsequence
int max_subsequence = 0;
for (int i = 0; i < arr.length;
i++) {
// Store the length of LIPS
// by choosing the closest prime
// number smaller than arr[i]
dp[i][0] = (arr[i] >= 2) ? 1 : 0;
// Store the length of longest LIPS
// by choosing the closest prime
// number greater than arr[i]
dp[i][1] = 1;
for (int j = 0; j < i; j++) {
// Store closest smaller
// prime number
Integer option1 = set.floor(arr[j]);
// Store closest prime number
// greater or equal
Integer option2 = set.ceiling(arr[j]);
// Recurrence relation
// Fill the value of dp[i][0]
if (option1 != null
&& option1 < set.floor(arr[i]))
dp[i][0]
= Math.max(dp[i][0], dp[j][0] + 1);
if (option2 != null
&& option2 < set.floor(arr[i]))
dp[i][0]
= Math.max(dp[i][0], dp[j][1] + 1);
// Fill the value of dp[i][1]
if (option1 != null
&& option1 < set.ceiling(arr[i]))
dp[i][1]
= Math.max(dp[i][0], dp[j][0] + 1);
if (option2 != null
&& option2 < set.ceiling(arr[i]))
dp[i][1]
= Math.max(dp[i][1], dp[j][1] + 1);
}
// Store the length of the longest
// increasing prime subsequence
max_subsequence
= Math.max(max_subsequence, dp[i][0]);
max_subsequence
= Math.max(max_subsequence, dp[i][1]);
}
return max_subsequence;
}
// Function to generate all prime numbers
public static void prime_sieve()
{
// Store all prime numbers
boolean primes[]
= new boolean[1000000 + 5];
// Consider all prime numbers
// to be true initially
Arrays.fill(primes, true);
// Mark 0 and 1 non-prime
primes[0] = primes[1] = false;
// Set all even numbers to
// non-prime
for (int i = 4; i <= 1000000;
i += 2)
primes[i] = false;
for (int i = 3; i <= 1000000;
i += 2) {
// If current element is prime
if (primes[i]) {
// Update all its multiples
// as non-prime
for (int j = 2 * i; j <= 1000000;
j += i)
primes[j] = false;
}
}
// Mark 2 as prime
set.add(2);
// Add all primes to the set
for (int i = 3; i <= 1000000;
i += 2)
if (primes[i])
set.add(i);
}
// Driver Code
public static void main(String args[])
{
int N = 6;
int arr[] = { 6, 7, 8, 9, 10, 11 };
prime_sieve();
System.out.println(LIPS(arr, N));
}
}
输出：
3
时间复杂度：O(N ^ 2 logN)。
辅助空间：O(n)。
版权属于：月萌API www.moonapi.com，转载请注明出处
