# Profit Maximization based on dynamix programming

I have been trying to solve this problem :
" You have to travel to different villages to make some profit.
In each village, you gain some profit. But the catch is, from a particular village i, you can only move to a village j if and only if and the profit gain from village j is a multiple of the profit gain from village i.

You have to tell the maximum profit you can gain while traveling."

Here is the link to the full problem:

I have been trying to solve this problem for some time. I know this is a variant of the longest increasing subsequence but the first thought that came to my mind was to solve it through recursion and then memoize it. Here is a part of the code to my approach. Please help me identify the mistake.

``````    int[] dp;
int index;
int solve(int[] p) {
int n = p.length;
int max = 0;
for(int i = 0;i<n; i++)
{
dp = new int[i+1];
Arrays.fill(dp,-1);
index = i;
max = Math.max(max,profit(p,i));
}
return max;
}
int profit(int[] p, int n)
{
if(dp[n] == -1)
{
if(n == 0)
{
if(p[index] % p[n] == 0)
dp[n] = p[n];
else
dp[n] = 0;
}
else
{
int v1 = profit(p,n-1);
int v2 = 0;
if(p[index] % p[n] == 0)
v2 = p[n] + profit(p,n-1);
dp[n] = Math.max(v1,v2);
}
}
return dp[n];
}
``````

int solve (int n,vector arr) {
long long dp[n];
dp=arr;
for(int i=1;i<n;i++)
{
dp[i]=arr[i];
for(int j=0;j<i;j++)
{
if(arr[j]<arr[i] && (arr[i]%arr[j])==0)
dp[i]=max(dp[i],dp[j]+arr[i]);
}
}
long long res=0;
for(int i=0;i<n;i++)
res=max(res,dp[i]);
return res;
}

int solve (int N,int p_i[])
{
int num=p_i;
int sum=0;
for(int i=0;i<N;i++)
{
if(p_i[i]%num==0)
{
sum += p_i[i];
num=p_i[i];
}
}
return sum;

}

int main()
{
int N;
scanf("%d",&N);
int i;
int p_i[N];
for(i=0;i<N;i++)
{
scanf("%d", &p_i[i]);

``````}
int out= solve(N,p_i);
printf("%d",out);

return 0;
``````

}