package hackerrank;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * https://www.hackerrank.com/challenges/stockmax
 */
public class StockMaximize {
    private static long maxProfit(long[] prices) {
        return maxProfit(prices, 0, 0, new HashMap<>());
    }

    private static long maxProfit(long[] prices, int day, long shares, Map<String, Long> memo) {
        if (day == prices.length) {
            return 0;
        }
        String key = day + "|" + shares;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        long buy = maxProfit(prices, day + 1, shares + 1, memo) - prices[day];
        long skip = maxProfit(prices, day + 1, shares, memo);
        long sell = maxProfit(prices, day + 1, 0, memo) + (shares * prices[day]);
        long max = Math.max(buy, Math.max(sell, skip));
        memo.put(key, max);
        return max;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int testCases = in.nextInt();
        for (int t = 0; t < testCases; t++) {
            int n = in.nextInt();
            long[] prices = new long[n];
            for (int i = 0; i < n; i++) {
                prices[i] = in.nextLong();
            }
            System.out.println(maxProfit(prices));
        }
    }
}

@@ -18,56 +18,8 @@
 k;%0A%0A
-import java.util.HashMap;%0Aimport java.util.Map;%0A
 impo
@@ -191,567 +191,201 @@
     
-return maxProfit(prices, 0, 0, new HashMap%3C%3E())
+long maxSoFar = 0
 ;%0A    
-%7D%0A%0A
     
-private static 
 long 
-maxP
+p
 rofit
-(long%5B%5D prices, int day, long shares, Map%3CString, Long%3E memo) %7B%0A        if (day == prices.length) %7B%0A            return 0;%0A        %7D%0A        String key = day + %22%7C%22 + shares;%0A        if (memo.containsKey(key)) %7B%0A            return memo.get(key);%0A        %7D%0A        long buy = maxProfit(prices, day + 1, shares + 1, memo) - prices%5Bday%5D;%0A        long skip = maxProfit(prices, day + 1, shares, memo);%0A        long sell = maxProfit(prices, day + 1, 0, memo) + (shares *
+ = 0;%0A        for (int i = prices.length - 1; i %3E= 0; i--) %7B%0A            maxSoFar = Math.max(prices%5Bi%5D, maxSoFar);%0A            profit += maxSoFar -
  prices%5B
 day%5D
@@ -384,13 +384,10 @@
 ces%5B
-day%5D)
+i%5D
 ;%0A  
@@ -396,83 +396,9 @@
     
-long max = Math.max(buy, Math.max(sell, skip));%0A        memo.put(key, max);
+%7D
 %0A   
@@ -409,19 +409,22 @@
  return 
-max
+profit
 ;%0A    %7D%0A

Solve Stock Maximize