Commit09ec18b

applewjg

committed

BestTimetoBuyandSellStock*

Change-Id: I37a3b8ddeecc253528579180fadfaa8c996c6944

1 parenta23170f commit09ec18bCopy full SHA for 09ec18b

File tree

+90

-0

lines changed

+90

-0

lines changed

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,26 @@`
	`1`	`+/*`
	`2`	`+ Author: King, higuige@gmail.com`
	`3`	`+ Date: Oct 07, 2014`
	`4`	`+ Problem: Best Time to Buy and Sell Stock`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: http://leetcode.com/onlinejudge#question_121`
	`7`	`+ Notes:`
	`8`	`+ Say you have an array for which the ith element is the price of a given stock on day i.`
	`9`	`+ If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock),`
	`10`	`+ design an algorithm to find the maximum profit.`
	`11`	`+`
	`12`	`+ Solution: For each element, calculate the max difference with the former elements.`
	`13`	`+ */`
	`14`	`+`
	`15`	`+publicclassSolution {`
	`16`	`+publicintmaxProfit(int[]prices) {`
	`17`	`+intn =prices.length;`
	`18`	`+if (n <=1)return0;`
	`19`	`+intres =0,minVal =prices[0];`
	`20`	`+for (inti =1;i <n; ++i) {`
	`21`	`+res =Math.max(res,prices[i] -minVal);`
	`22`	`+minVal =Math.min(minVal,prices[i]);`
	`23`	`+ }`
	`24`	`+returnres;`
	`25`	`+ }`
	`26`	`+}`

Lines changed: 25 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,25 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Jan 02, 2015`
	`4`	`+ Problem: Best Time to Buy and Sell Stock II`
	`5`	`+ Difficulty: Medium`
	`6`	`+ Source: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/`
	`7`	`+ Notes:`
	`8`	`+ Say you have an array for which the ith element is the price of a given stock on day i.`
	`9`	`+ Design an algorithm to find the maximum profit. You may complete as many transactions as you like`
	`10`	`+ (ie, buy one and sell one share of the stock multiple times).`
	`11`	`+ However, you may not engage in multiple transactions at the same time`
	`12`	`+ (ie, you must sell the stock before you buy again).`
	`13`	`+`
	`14`	`+ Solution: 1. At the beginning of the ascending order: buy.`
	`15`	`+ At the ending of the ascending order: sell.`
	`16`	`+ */`
	`17`	`+publicclassSolution {`
	`18`	`+publicintmaxProfit(int[]prices) {`
	`19`	`+intres =0;`
	`20`	`+for (inti =1;i <prices.length; ++i) {`
	`21`	`+res +=Math.max(0,prices[i] -prices[i-1]);`
	`22`	`+ }`
	`23`	`+returnres;`
	`24`	`+ }`
	`25`	`+}`

Lines changed: 39 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,39 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Jan 02, 2015`
	`4`	`+ Problem: Best Time to Buy and Sell Stock III`
	`5`	`+ Difficulty: Medium`
	`6`	`+ Source: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/`
	`7`	`+ Notes:`
	`8`	`+ Say you have an array for which the ith element is the price of a given stock on day i.`
	`9`	`+ Design an algorithm to find the maximum profit. You may complete at most two transactions.`
	`10`	`+ Note:`
	`11`	`+ You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).`
	`12`	`+`
	`13`	`+ Solution: dp. max profit = max { l2r[0...i] + r2l[i+1...N-1] }.`
	`14`	`+ 0 <= i <= N-1`
	`15`	`+ */`
	`16`	`+`
	`17`	`+publicclassSolution {`
	`18`	`+publicintmaxProfit(int[]prices) {`
	`19`	`+intn =prices.length;`
	`20`	`+if (n <=1)return0;`
	`21`	`+int[]l2r =newint[n];`
	`22`	`+int[]r2l =newint[n];`
	`23`	`+l2r[0] =0;r2l[n-1] =0;`
	`24`	`+intminVal =prices[0],maxVal =prices[n-1];`
	`25`	`+for (inti =1;i <n; ++i) {`
	`26`	`+l2r[i] =Math.max(l2r[i-1],prices[i] -minVal);`
	`27`	`+minVal =Math.min(minVal,prices[i]);`
	`28`	`+ }`
	`29`	`+for (inti =n -2;i >=0; --i) {`
	`30`	`+r2l[i] =Math.max(r2l[i+1],maxVal -prices[i]);`
	`31`	`+maxVal =Math.max(maxVal,prices[i]);`
	`32`	`+ }`
	`33`	`+intres =l2r[n-1];`
	`34`	`+for (inti =0;i <n -1; ++i) {`
	`35`	`+res =Math.max(res,l2r[i] +r2l[i+1]);`
	`36`	`+ }`
	`37`	`+returnres;`
	`38`	`+ }`
	`39`	`+}`

Comments

(0)