Why the answer is 7?


  • 1
    S

    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!


  • 0
    S

    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


  • 0
    M

    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.


  • 0
    Y

    I think the answer is that (3-1)+(7-2) = 7.


  • 0
    D

    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).


  • 0
    H
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.