Say you have an array for which the

i^{th}element is the price of a given stock on dayi.If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell.

It is a question from Hacking a Google Interview from MIT handout #3 titled “Beating the Stock Market“.

At first glance, you might think that finding the minimum and maximum value would do, but it does have a hidden restriction, that is: You must buy before you can sell.

The question is equivalent to the following:

*i*and

*j*that maximizes A

*– A*

_{j}*, where*

_{i}*i*<

*j*.

There is an obvious *O*(*N*^{2}) solution, but in fact we can do better in just *O*(*N*).

To solve this problem efficiently, you would need to track the minimum value’s index. As you traverse, update the minimum value’s index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
void getBestTime(int stocks[], int sz, int &buy, int &sell) { int min = 0; int maxDiff = 0; buy = sell = 0; for (int i = 0; i < sz; i++) { if (stocks[i] < stocks[min]) min = i; int diff = stocks[i] - stocks[min]; if (diff > maxDiff) { buy = min; sell = i; maxDiff = diff; } } } |

Actually this is an easy question. People may learn this in data structure course. Though, your solution still good an elegant. Like it.

-24Yeah it is easy but I also like how easy it is to fall into the trap if you're not careful. Really? Did you learn it in a data structure course? I did not. How would you classify this question? I don't think it's DP (ie, it does not have overlapping sub-problems). Correct me if I'm wrong.

+6Suppose D[i] is the maximum income when sell at price A[i], then

D[i] = max_{k <= i}{A[i] – A[k]} and if i==0, D[0]=0

and

D[i+1] = (A[i+1]-A[i]) + Math.max(D[i],0) //Runtime:O(n)

finally

maximum income is max_{i=[0,n)}{D[i]}

+1+11hey 1337coder,

i was given an interview question on this, but they had a following question: if you can keep buying and selling, how to maximize the profit? for example, if it is 6,1,3,2,4,7, we can buy for 1 and sell for 3, and we can buy for 2, and sell for 4,then buy on 4, sell for 7. total maxval =3-1+4-2+7-4 = 7. They would like to have some O(n) solutions.

+2-2I intended to copy the second while loop as:

0public class Solution {

public int maxProfit(int[] prices) {

int max = 0;

for(int i = 0; i < prices.length – 1; i++) {

max += Math.max(0, prices[i+1] – prices[i]);

}

return max;

}

}

+1Why not start your loop from 1 not from 0, 1337c0d3r?

0what does this kind of question falls into (some category)?

0int[] stocks = { 2, 2, 6, 5, 1, 4 } for this input the buy should be at index 4 and sell should be at index 6. however your code return index 0 for buy (which is wrong) and index 2 for sell.

-4Above code is correct .. You should buy first ..then only you can sell..

+1never mind…..please ignore my last post

-1#include

#include

int main ()

{

extern void trade(int * ,int);

int arr[]={6,1,3,2,4,7};

trade(arr,sizeof(arr)/sizeof(arr[0]));

getch();

return 0;

}

void trade(int *p,int size){

int b=0,s=0,min,profit=0,i,buy=0;

min=p[0];

for(i=0;i<size;i++)

{

if(p[i]profit)

{

buy=b;

s=i;

profit=p[i]-min;

}

}

printf(“buy on %d , sell on %d ..profit %d \n”,buy,s,profit);

}

-1-1void getMaxProfit(int stocks[], int N) {

if (N <2) return 0;

int prev = stocks[0];

int bought = -1;

int profit = 0;

for(int i = 0; i stocks[prev] ) {

if (bought < 0)

bought = stock[prev];

} else if(stocks[i] = 0) {

assert(stocks[prev] >= bought;

profit += stocks[prev] >= bought;

bought = -1;

}

}

prev = i;

}

return profit;

}

0I think it is safe to put the following into a “else” block.

0this problem would be difficult and interesting if this is a data stream, not a given array.

0@Moussa:

If we put the code you mentioned in else block. It wont work for input like 1,2,3,4,5,6 where it will never enter the else block. COrrect me if i am wrong.

0public class Solution {

public int maxProfit(int[] prices)

{

if (prices==null||prices.length<=0)

return 0;

int profit = 0;

int high = prices[0];

int low = prices[0];

for(int i=1;ihigh)

{

high =prices[i];

profit = high-low;

}

else if (prices[i] -low >profit)

{

high = prices[i];

profit = high – low;

}

else if (prices[i]<low)

low = prices[i];

}

return profit;

}

}

0It is incorrect. The code will course buy point behind sell point…..

-2Fail in this case

Input: [2,1,2,0,1]

Output: 1

Expected: 2

0The easiest and fastest correct answer is this:

0Sorry, copy mistake,

-1Something wrong with

`tag...`

int result = 0;

for(int i = 1; i 0 ) {

result += diff;

}

}

return result;

0public class Solution {

public int maxProfit(int[] prices) {

// Start typing your Java solution below

// DO NOT write main() function

// find a pattern which minimal price is before maxminal price

if (prices==null||prices.length<=0)

return 0;

int result = 0;

for(int i = 1; i 0 ) {

result += diff;

}

}

return result;

}

}

0I don’t know what’s wrong with the code I’m trying to copy and paste, it doesn’t look like the same as origin.

It’s simple and naive, just adds up together all positive neighborhood’s difference.

-1you can only buy and sell one time.

+1if you build an array of stocks[i] – stocks[i-1], this problem is converted to Maximum sub-array problem. and you can reduce the space to constant later

+1I could think of one more appraoch, Buy on a local minimum and sell on the local maximum. Lets say we have price array as [6,1,3,2,4,7]. I’ll buy at 1 and 2 (both local minimums) and sell at 3,7 (both local maximums). Does it sound okay ?

0public class Snippet {

public static void main(String[] args) {

getBestTime(new int[]{7, 1,2,3,4} );

}

static void getBestTime(int stocks[]) {

int min = 0;

int max = 0;

int maxDiff = 0;

int buy = 0;

int sell = 0;

for (int i = 0; i < stocks.length; i++) {

if (stocks[i] stocks[max])

max = i;

int diff = stocks[max] – stocks[min];

if (diff > maxDiff) {

buy = min;

sell = max;

maxDiff = diff;

}

}

System.out.println(“buy -> ” + stocks[buy] + ” sell -> ” + stocks[sell]);

}

}

0doesnt work.

0It’s does not work. It fails with test case: 5 10 3 30 7 50. Expected is buy at 7 and sell at 50.

0Why you buy at 7? You should be buying at 3 and this code works.

0if (prices.length > 1) {

int minVal = prices[0];

int maxVal = 0;

int maxDiff = 0;

for (int i = 0; i < prices.length; i++) {

if (prices[i] <= minVal) {

int temp = prices[i];

for (int j = i + 1; j < prices.length; j++, i++) {

if (prices[j] maxDiff) {

maxVal = prices[j];

minVal = temp;

maxDiff = Math.abs(prices[j] – temp);

}

}

}

else if (prices[i] > maxVal)

maxVal = prices[i];

}

return maxVal > 0 ? maxVal – minVal : 0;

}

return 0;

0This shows wrong answer for the following test case apparently :

Input : [6,1,3,2,4,7]

Output : 7

Expected : 6

Can anyone please explain to me my fault?

+1You are only allowed to make one transaction. So the ans would be, buy at 1, sell at 5 (profit = 7-1=6)

0So how do you account for a day that the stock prices only drop. For example:

prices = [43, 41, 35, 27, 19, 12, 5, 2]

Ideally, if you are required to buy and sell in that day. You would want to minimize the loss. Your max profit would be -2 in this array and your buy would be at index 0 and sell would be at index 1. Your algorithm never returns less than 0. In my last interview this came up and they still wanted a O(n) solution. I could make it work easily with 2 nested for loops O(n^2) but couldn’t figure out how to keep it O(n). Any ideas?

0多くの探検家選択を探検装備のボル表、今度は究極の腕時計を探検運動。FiremanストームChaser腕時計も獲得しアメリカ竜巻研究家の胡文博士の同情。この黒い表面の腕時計をして新しい多機能クロノ発揮はクロノメーターのほか、余分に提供した速度計と距離計の実用的な機能になるとなり、勇敢な「群れ者”たちの装備の一つ。スーパーコピーまた以前発表したEngineer DiverⅡＧＭＴも登場し、この採用DLCめっきとアナログ時計バンドの限界潜水しジオン·乃瑞潜など113メートルの深海、再び世界記録を破った素手で潜水。そのマイナス４０度抗低温の能力も確保でき、潜水勇士寒い深海で正確な時間を把握する。 http://www.newkakaku.com/lb5.htm

0To embed your code, please use

.

0