0 like 0 dislike
3,682 views

retagged | 3,682 views

0 like 0 dislike

Question :

Find the subsequence from an array with highest score. Score is the sum of f(x) for all the elements of the subsequence.

f(x) = number of divisors of 'x'.

For , a[i] and a[i+1] in the selected subsequence , one of the following should be true :

a[i] = 2*a[i+1]

or

a[i] = 3*a[i+1]

or

a[i] = a[i] + 1 or a[i] = a[i] - 1

or

a[i] = a[i]/3 ( must be divisible by 3)

or

a[i] = a[i]/2 ( must be divisible by 2)

Input :

10
2 3 4 5 6 12 18 36 9 99

Output :

28

[2,3,4,5,6,12,36] is the selected subsequence from the array [2+2+3+4+2+7+8==28]

My code :

```// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ;
ll divi[200006];
ll fin[200005];
void findDivisors(ll n)
{
for (int i = 1; i <= n; i++) {
for (int j = 1; j * i <= n; j++)
divi[i * j]++;
}
}

int main()
{
ll r = 0 ;
int n = 100000+7;
findDivisors(n);
cin>>n;
int i = 1 ;
while(i<=n)
{
int x ;
cin>>x ;
ll current = divi[x] ;
ll maxi = 0 ;
if(x%2==0)
{
maxi = max(maxi,fin[x/2]);
}
if(x%3==0)
{
maxi = max(maxi,fin[x/3]);
}
maxi = max(maxi,fin[x-1]);
maxi = max(maxi,fin[x+1]);
maxi = max(maxi,fin[2*x]);
maxi = max(maxi,fin[3*x]);
ll answer = current + maxi ;