Stock Maximize Discussions | Algorithms | HackerRank
  • [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;
    }