LICPS

Problem Statement

LICPS Problem Description You are given an array Arr of N integers. Find the length of the longest good subsequence S of Arr. A subsequence S keeps the original order of the array: it is obtained by choosing indices i1 < i2 < ... < ik and taking Arr[i1], Arr[i2], ..., Arr[ik]. S is called good when both rules hold: S is strictly increasing : Arr[i1] < Arr[i2] < ... < Arr[ik]. Every two consecutive elements of S are coprime : gcd(Arr[it], Arr[it+1]) = 1 for every t from 1 to k-1. (inferred - the coprime rule is applied to consecutive elements of S; this is the reading under which every example below holds.) Note: two integers A and B are coprime when no integer x greater than 1 divides both of them, that is, gcd(A, B) = 1. (inferred - the qualifier x > 1 is required: 1 divides every integer, so without it no pair of integers would ever be coprime.) In particular gcd(1, B) = 1 for every B, so the value 1 is coprime with every value. A subsequence of length 1 is alway