Amazon HackerRank OA

第三题提示的是DP，但怎么感觉不需要用DP的方法。。。

贴个AC的代码：

1.         /*
   
2.          * Facts: If the price at day `j` is the maximum one among all prices, we can keep buying from day 0 to day j and get the maximum profits for day 0 to j. The best strategy has to be selling on day j. Then we know day 0 - j does not need to be considred anymore and we move to j+1 and the previous fact holds again.
   
3.          * Implementation: scan from right to left and keep updating `max` value (max is always the maximum price between current index and the right-most index). At a given index `j`, two possiblities can happen:
   
4.          * 1. if prices[j] < max, add the difference into the profits
   
5.          * 2. if prices[j] >= max, all items to the right of j can be discarded
   
6.          */
   
7.        
   
8.     public static void main(String[] args) {
   
9.         Scanner sc = new Scanner(System.in);
   
10.         int T = sc.nextInt();
    
11.         for(int i=0; i<T; i++) {
    
12.             int N = sc.nextInt();
    
13.             int[] prices = new int[N];
    
14.             for(int j=0; j<N; j++) {
    
15.                 prices[j] = sc.nextInt();
    
16.             }
    
17.             
    
18.             int max = 0;
    
19.             long profits = 0;
    
20.             for(int j=N-1; j>=0; j--) {
    
21.                 int diff = max - prices[j];
    
22.                 if(diff < 0) {
    
23.                     max = prices[j];
    
24.                 }
    
25.                 else {
    
26.                     profits += diff;
    
27.                 }
    
28.             }
    
29.             System.out.println(profits);
    
30.         }
    
31.         sc.close();
    
32.     }

复制代码

楼主怎么跟我的遭遇一样啊  做题时没有去查那题stock max 最后5分钟查了  结果来不及写了。。。也是题意错 其他两题都做出来了  希望跟你同样拿到onsite

def stockmax(prices):
    m = prices.pop()
    maxsum = 0  
    arrsum = 0
    for p in reversed(prices):
        m = max(m, p)
        maxsum+=m
        arrsum+=p
    return maxsum-arrsum