O(n) time, constant-space, total one time iterative, Java Solution


  • 0
    L

    http://www.gvace.com/2015/07/best-time-buy-sell-stock-iii/

    O(n) time, Constant Space, total one time iterative Solution:
    Keep tracking dist1,dist2,dist3,dist4,dist12

    dist1: last longest raise price

    dist2: second last longest raise price

    dist3: the new longest raise price

    dist4: (combination of dist2 and dist3) in the range of all elements in dist2 and dist3, the longgest raise price

    dist12: (combination of dist1 and dist2) in the range of all elements in dist1 and dist2, the longgest raise price

    Setps:

    First find dist1, and dist2

    Then each time when we see a raise, find the max from the following choices:

    {

    dist1+dist2 //keep the [last longest], and [second last longest] raise price

    dist2+dist3 //keep the [second last longest] raise price and [new longest raise price]

    dist12+dist3 //keep the [combination of dist1 and dist2] and [new longest raise price]

    dist1+dist4 //keep the [last longest] and [combination of dist2 and dist3]

    dist1+dist3 //keep the [last longest] and [new longest raise price]

    }

    When there is a raise(prices[p]>prices[p-1]),
    find the max = max(dist1+dist2,dist2+dist3,dist12+dist3,dist1+dist4,dist1+dist3)
    then update min,min1,min2,dist1,dist2,dist12 correspond with the choice


Log in to reply
 

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