the input is [6,1,3,2,4,7]
in my opnion,the max total is buy when value==1,and sell when value==7, then the max total is 7-1==6.but the web said the answer is 7!
i got it!
the question is a joke!
i misunderstand that if you want to buy ,you must sell at the time you buy it .
in above case,the question will be more complicate and interesting
Buy at 1, sell at 3. Buy at 2, sell at 7. (3-1)+(7-2) = 2+5 = 7. With this problem, you are not restricted to only one transaction. However, you need to sell what you are holding before you can buy more.
The accepted solution is a pairwise comparison only.
6,1 is not possible. 1,3 = profit of 2, total profit = 2 3,2 is not possible 2,3 = profit of 2, total profit = 4 4,7 = profit of 3, total profit = 7
this is the greedy approach because you are not finding the 'maximum possible solution' but the first 'reasonable' solution.
I think the question is worded a bit vaguely because an absolute maximum profit would only be possible in O(N^2). Anyway, such ambiguity lies in interviews as well.
Btw, without the greedy approach, the max absolute profit is still the same. (Or I could not find a test case to disprove it yet).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.