Stock Maximize Discussions | Algorithms | HackerRank
  • + 3 comments

    Actually I had a workaround for O(N*2) complexity and was able to solve using DP. It is important to notice that J(i,x) is of the form Ax + B, where i is the day, and x is the number of stocks at day i, J(i,x) is the maximum profit that can be made from day i till day N. Since J(i,x) is linear all we need is to evaluate is J(i,0) and J(i,1). So N*2 complexity drops down to 2*N!!

    my code for reference:

    long int **J;
    
    long int InvestReturn(long int i,long int x,long int *p,long int N){
    if (i==N) {
        J[N][x]=0;
        return 0;
    }
    if (J[i][x]!=-1) {
        return J[i][x];
    }
    long int A =InvestReturn(i+1,1,p,N)   -InvestReturn(i+1,0,p,N);
    long int B =InvestReturn(i+1,0,p,N);
    
    if (A-p[i]>0) { //buying one stock is opt.
        J[i][x] = -p[i]+A*(x+1)+B;
        return J[i][x];
    }else{ //selling all x stocks is optimal
        J[i][x] = x*p[i]+B;
        return J[i][x];
    }
    

    }

    • + 0 comments

      Amazing approach, I found it natural to write down the 2D problem but was having trouble making it performant. This approach makes it feasible!

    • + 0 comments

      I'm interested with this approach, yet I still not fully understand. Would you mind to elaborate more? Especially, what is A, what is B, and why Ax+B ?

      Thanks in advance.

    • [deleted]
      + 0 comments

      @merovinjean 's solution is a perfect and out of this world solution. I have to trace to understand how it works. This is the Java port:

      public static long InvestReturn(int i, int x, long[] prices, int num, long[][] jArr) {
          if (i == num) {
              jArr[num][x] = 0;
              return 0;
          }
          if (jArr[i][x] != -1) {
              return jArr[i][x];
          }
          long A = InvestReturn(i + 1, 1, prices, num, jArr);
          long B = InvestReturn(i + 1, 0, prices, num, jArr);
          A = A - B;
      
          if (A - prices[i] > 0) { //buying one stock is optimal
              jArr[i][x] = -prices[i] + A * (x + 1) + B;
              return jArr[i][x];
          } else { //selling all x stocks is optimal
              jArr[i][x] = x * prices[i] + B;
              return jArr[i][x];
          }
      }
      
      public static long InvestReturn(long[] prices) {
           long[][] jArr = new long[prices.length+1][2];
           for (int i = 0; i < jArr.length; i++) {
              jArr[i][0] = -1;
              jArr[i][1] = -1;
           }
      
           return InvestReturn(0, 0, prices, prices.length, jArr);
      }
      

      I think it is equivalent to this:

      public static long InvestReturn(long[] prices) {
          long profitNowPlusMaxPrice = 0;
          long profitNow = 0;
      
          for (int i = prices.length - 1; i > -1; i--) {
              long maxPrice = profitNowPlusMaxPrice - profitNow;
      
              if (maxPrice > prices[i]) {
                  // buying is optimal
                  profitNowPlusMaxPrice = (maxPrice * (1 + 1)) - prices[i] +  profitNow;
                  profitNow = (maxPrice * (0 + 1)) - prices[i] + profitNow;
      
              } else {
                  // current price is max, replace max price
                  profitNowPlusMaxPrice = (1 * prices[i]) + profitNow;
                  profitNow = (0 * prices[i]) + profitNow;
              }
          }
      
          return profitNow;
      }