Commit79cf9eb

committed

Add divide and conquer example: best time to buy and sell stocks.

1 parent4973392 commit79cf9ebCopy full SHA for 79cf9eb

File tree

-3

lines changed

-3

lines changed

Lines changed: 3 additions & 3 deletions

Original file line number	Diff line number	Diff line change
@@ -37,7 +37,7 @@ _Explanation:_ In this case, no transaction is done, i.e. max `profit = 0`.
`37`	`37`
`38`	`38`	`##Possible Solutions`
`39`	`39`
`40`		`-###Divide and conquer approach`
	`40`	+###Divide and conquer approach`O(2^n)`
`41`	`41`
`42`	`42`	`We may tryall combinations of buying and selling and find out the most profitable one by applying_divide and conquer approach_.`
`43`	`43`
@@ -62,7 +62,7 @@ As you may see, this is very inefficient. For example for just `20` prices the n
`62`	`62`
`63`	`63`	If we avoid cloning the prices array between recursive function calls and will use the array pointer then additional space complexity will be proportional to the depth of the recursion:`O(n)`
`64`	`64`
`65`		`-##Peak Valley Approach`
	`65`	+##Peak Valley Approach`O(n)`
`66`	`66`
`67`	`67`	If we plot the prices array (i.e.`[7, 1, 5, 3, 6, 4]`) we may notice that the points of interest are the consecutive valleys and peaks
`68`	`68`
`@@ -82,7 +82,7 @@ Since the algorithm requires only one pass through the prices array, the time co`
`82`	`82`
`83`	`83`	Except of the prices array itself the algorithm consumes the constant amount of memory. Thus, additional space complexity is`O(1)`.
`84`	`84`
`85`		`-##Accumulator Approach`
	`85`	+##Accumulator Approach`O(n)`
`86`	`86`
`87`	`87`	There is even simpler approach exists. Let's say we have the prices array which looks like this`[1, 7, 2, 3, 6, 7, 6, 7]`:
`88`	`88`

Comments

(0)