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

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

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