To The Moon!

Problem Statement:

X Æ A-15 Musk, the richest person on Mars, is an avid investor. His army of Tesla Bots has devised an algorithm to accurately predict the share price of Frozen Banana Corporation (FBC) for the next few days. Now unstoppable, he has decided to invest in FBC and wants to know the maximum profit he can make by buying and selling the stock.

Each day, he can either buy one share of FBC, sell any number of shares of FBC that he owns, or not make any transaction at all. What is the maximum profit he can obtain with an optimum trading strategy?

Input Format:

• The first line contains the number of test cases T.
• For each of the T test cases:
  • The first line contains an integer N, the number of days predicted.
  • The second line contains N space-separated integers, P_i, the price of FBC on the i^th day.

Output Format:

For each test case, output a single line containing the maximum profit that X Æ A-15 Musk can make.

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 5 * 10⁴
• 1 ≤ P_i ≤ 10⁵

Sample Input:

3
3
5 3 2
3
1 2 100
4
1 3 1 2

Sample Output:

0
197
3

Explanation:

For the first case, there is no profit because the share price never rises, return 0.

For the second case, buy one share on the first two days and sell both of them on the third day for a profit of 197.

For the third case, buy one share on day 1, sell one on day 2, buy one share on day 3, and sell one share on day 4. The overall profit is 3.

Solution:

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

for _ in range(int(input())):
    n = int(input())
    arr = list(map(int,input().split()))
    print(int(max_profit(arr)))