title: Profit Maximization based on dynamix programming
body: <p>I have been trying to solve this problem :
  &quot; 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.</p>
  <p>You have to tell the maximum profit you can gain while traveling.&quot;</p>
  <p>Here is the link to the full problem:
  <a href="https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/avatar-and-his-quest-d939b13f/description/" rel="nofollow noreferrer">https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/avatar-and-his-quest-d939b13f/description/</a></p>
  <p>I have been trying to solve this problem for quite a few hours. 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.</p>
  <pre class="lang-java prettyprint-override"><code>    static int[] dp;
      static int index;
      static int solve(int[] p) {
          int n = p.length;
          int max = 0;
          for(int i = 0;i&lt;n; i++)
          {
              dp = new int[i+1];
              Arrays.fill(dp,-1);
              index = i;
              max = Math.max(max,profit(p,i));
          }
          return max;
      }
      static 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];
      }
  </code></pre>