https://www.acmicpc.net/problem/11501
initial
i couldnt solve this
12423
I thought of finding the max value of the list and selling all the bought stocks at that day. That would work for 124 but what about the rest like 23? We evidently need to buy the stock at 2 sell at 3 for additional profit but my way would not work.
So we know that we need to sell stocks when the value is bigger than what we have encountered before. But I coudlnt think of the implementation.
But if we reverse the list, we can easily think of the pattern. We set tmp as the first element and if the iter element is smaller than tmp, we know that since it is reversed, we can buy at a cheaper (smaller) price and sell at tmp price (profit+= tmp-lst[i]). Else, if it is bigger than tmp, like 12432, then 3 is bigger than 2 so we shouldnt buy 3 and sell at 2 cuz it is a loss, not a profit. In that case, we set tmp as that big value (tmp=lst[i]) and see if the next iter elements are smaller than this big tmp value, and if it is we can sell at this tmp price.
(i thought of thinking backwards like that min number of steps to reach a storey DP where you think of coming from the previous step. But i couldnt think of reversing the list and simplifying the impl)
solution
t = int(input())
for _ in range(t):
n = int(input())
lst = list(map(int, input().split()))
lst.reverse()
tmp = lst[0]
profit = 0
for i in range(1, n):
if lst[i] < tmp:
profit += tmp - lst[i]
else:
tmp = lst[i]
print(profit)revisited jan 25th
i couldnt solve this agn. I feel a lot of greedy questions if ur stuck try thinking backwards like reversing a list of sorting list reversed.
the init explanation is good.
revisited may 22nd
i couldnt solve again lol reread my explanation
complexity
The time complexity of your code is O(n), where n is the number of stock prices. This is because you iterate through the list of stock prices once, processing each price exactly once.
The space complexity is O(1), as you are using a constant amount of additional memory to store variables like tmp, profit, and loop variables. The list lst is reversed in-place, so it doesn't contribute to the space complexity.
Overall, your code is efficient and has a linear time complexity, making it suitable for handling a large number of stock prices.
