|
Given an array arr[], find the length of the longest strictly decreasing subsequence such that no two adjacent elements are coprime.
Examples:
Input: N = 5, arr[]= {9, 6, 4, 3, 2}
Output: 4
Explanation: The longest strictly decreasing non-coprime subsequence is {9, 6, 4, 2} having length = 4.
Input: N=4, arr[]={6, 4, 2, 1}
Output: 3
Explanation: The longest strictly decreasing non-coprime subsequence is {6, 4, 2} having length = 3.
Approach: To solve the problem, follow the below idea:
The approach is to use Dynamic Programming to find the length of the longest decreasing non-coprime subsequence for a given array of integers. The approach involves iterating through each element of the array and, for each element, considering its divisors to update a dynamic programming table (dp) that keeps track of the longest decreasing non-coprime subsequence ending at each divisor.
Step-by-step algorithm:
- Iterate through each element of the array in reverse order.
- For each element a[i], find its divisors and update the local subsequence (lcs) by checking the dynamic programming table (dp) for each divisor.
- Update the longest subsequence (lgs) by taking the maximum of the current lcs + 1 and the existing lgs.
- Update the dynamic programming table (dp) for each divisor by storing the maximum of the current value and lcs + 1.
Below is the implementation of the above approach:
C++
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX_N = 100001;
int arr[MAX_N];
int dp[MAX_N];
int getSubsequence(int n)
{
int lgs = 0;
for (int i = n ; i > 0; i--) {
int x = arr[i];
int lcs = 0;
for (int j = 1; j * j <= x; j++) {
if (x % j == 0) {
if (j > 1) {
lcs = max(lcs, dp[j]);
}
lcs = max(lcs, dp[x / j]);
}
}
lgs = max(lgs, lcs + 1);
for (int j = 1; j * j <= x; j++) {
if (x % j == 0) {
dp[j] = max(dp[j], lcs + 1);
dp[x / j] = max(dp[x / j], lcs + 1);
}
}
}
return lgs;
}
int main()
{
int n = 4;
int input[] = { 6, 4, 2, 1 };
for(int i = 0; i < 4; i++) {
arr[i + 1] = input[i];
}
int result = getSubsequence(n);
cout << result;
return 0;
}
|
Java
import java.util.Arrays;
public class Main {
static final int MAX_N = 100001;
static int[] arr = new int[MAX_N];
static int[] dp = new int[MAX_N];
static int getSubsequence(int n) {
int lgs = 0;
for (int i = n; i > 0; i--) {
int x = arr[i];
int lcs = 0;
for (int j = 1; j * j <= x; j++) {
if (x % j == 0) {
if (j > 1) {
lcs = Math.max(lcs, dp[j]);
}
lcs = Math.max(lcs, dp[x / j]);
}
}
lgs = Math.max(lgs, lcs + 1);
for (int j = 1; j * j <= x; j++) {
if (x % j == 0) {
dp[j] = Math.max(dp[j], lcs + 1);
dp[x / j] = Math.max(dp[x / j], lcs + 1);
}
}
}
return lgs;
}
public static void main(String[] args) {
int n = 4;
int[] input = {6, 4, 2, 1};
for (int i = 0; i < 4; i++) {
arr[i + 1] = input[i];
}
int result = getSubsequence(n);
System.out.println(result);
}
}
|
C#
using System;
class Program
{
const int MAX_N = 100001;
static int[] arr = new int[MAX_N];
static int[] dp = new int[MAX_N];
static int GetSubsequence(int n)
{
int lgs = 0;
for (int i = n; i > 0; i--)
{
int x = arr[i];
int lcs = 0;
for (int j = 1; j * j <= x; j++)
{
if (x % j == 0)
{
if (j > 1)
{
lcs = Math.Max(lcs, dp[j]);
}
lcs = Math.Max(lcs, dp[x / j]);
}
}
lgs = Math.Max(lgs, lcs + 1);
for (int j = 1; j * j <= x; j++)
{
if (x % j == 0)
{
dp[j] = Math.Max(dp[j], lcs + 1);
dp[x / j] = Math.Max(dp[x / j], lcs + 1);
}
}
}
return lgs;
}
static void Main()
{
int n = 4;
int[] input = { 6, 4, 2, 1 };
for (int i = 0; i < 4; i++)
{
arr[i + 1] = input[i];
}
int result = GetSubsequence(n);
Console.WriteLine(result);
}
}
|
Javascript
const MAX_N = 100001;
let arr = new Array(MAX_N).fill(0);
let dp = new Array(MAX_N).fill(0);
function getSubsequence(n) {
let lgs = 0;
for (let i = n; i > 0; i--) {
let x = arr[i];
let lcs = 0;
for (let j = 1; j * j <= x; j++) {
if (x % j == 0) {
if (j > 1) {
lcs = Math.max(lcs, dp[j]);
}
lcs = Math.max(lcs, dp[x / j]);
}
}
lgs = Math.max(lgs, lcs + 1);
for (let j = 1; j * j <= x; j++) {
if (x % j == 0) {
dp[j] = Math.max(dp[j], lcs + 1);
dp[x / j] = Math.max(dp[x / j], lcs + 1);
}
}
}
return lgs;
}
function main() {
let n = 4;
let input = [6, 4, 2, 1];
for (let i = 0; i < 4; i++) {
arr[i + 1] = input[i];
}
let result = getSubsequence(n);
console.log(result);
}
main();
|
Python3
import math
MAX_N = 100001
arr = [0] * MAX_N
dp = [0] * MAX_N
def getSubsequence(n):
lgs = 0
for i in range(n, 0, -1):
x = arr[i]
lcs = 0
for j in range(1, int(math.sqrt(x)) + 1):
if x % j == 0:
if j > 1:
lcs = max(lcs, dp[j])
lcs = max(lcs, dp[x // j])
lgs = max(lgs, lcs + 1)
for j in range(1, int(math.sqrt(x)) + 1):
if x % j == 0:
dp[j] = max(dp[j], lcs + 1)
dp[x // j] = max(dp[x // j], lcs + 1)
return lgs
def main():
n = 4
input_sequence = [6, 4, 2, 1]
for i in range(4):
arr[i + 1] = input_sequence[i]
result = getSubsequence(n)
print(result)
if __name__ == "__main__":
main()
|
Time Complexity: O(N * sqrt(max_element)), where N is the number of elements in the array and max_element is the maximum element of the array.
Auxiliary Space: O(max_element)
|
