121. Best Time to Buy and Sell Stock

  • 40.0%

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

1
2
3
4
5
6
Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
1
2
3
4
5
6
Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

两种思路:

  1. 寻找低谷与峰值之间的差。设置一个变量为低谷,vally,另一个变量为目前找到的最大值,maxsofar,则从头开始遍历,如果当前值小于vally,则此值与vally的差为负,所以vally改为当前值,如果当前值大于vally,则计算当前值与vally的差。一次遍历。
  2. 第二种思路,重新设置一个数组,记录邻近两个数字的差,类似于寻找最长的数组。

方法一:

微策略面试题

我的代码实现:

Oct 17, 2017

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = INT_MAX;
int maxPro = 0;
for(auto price:prices){
minPrice = min(price, minPrice);
maxPro = max(maxPro, price - minPrice);
}
return maxPro;
}
};

https://discuss.leetcode.com/topic/5863/sharing-my-simple-and-clear-c-solution

Sharing my simple and clear C++ solution

1
2
3
4
5
6
7
8
9
int maxProfit(vector<int> &prices) {
int maxPro = 0;
int minPrice = INT_MAX; // 此处不能用prices[0]代替,如果用,需要先判断prices.size()与0的关系
for(int i = 0; i < prices.size(); i++){
minPrice = min(minPrice, prices[i]);
maxPro = max(maxPro, prices[i] - minPrice);
}
return maxPro;
}

minPrice is the minimum price from day 0 to day i. And maxPro is the maximum profit we can get from day 0 to day i.

How to get maxPro? Just get the larger one between current maxPro and prices[i] - minPrice.

方法二:

https://discuss.leetcode.com/topic/5863/sharing-my-simple-and-clear-c-solution/5

Very nice solution! But it still can be optimized. We only need to calculate either maxProfit or minPrice not both in every loop. Running time can be dropped by 33% percent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProfit(int[] prices) {
if(prices == null || prices.length < 2) return 0;
int maxProfit = 0, minPrice = prices[0];

for(int i = 1; i < prices.length; i++) {
if(prices[i] > prices[i - 1]) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
} else {
minPrice = Math.min(minPrice, prices[i]);
}
}

return maxProfit;
}

cpp


https://discuss.leetcode.com/topic/5863/sharing-my-simple-and-clear-c-solution

Sharing my simple and clear C++ solution

1
2
3
4
5
6
7
8
9
int maxProfit(vector<int> &prices) {
int maxPro = 0;
int minPrice = INT_MAX;
for(int i = 0; i < prices.size(); i++){
minPrice = min(minPrice, prices[i]);
maxPro = max(maxPro, prices[i] - minPrice);
}
return maxPro;
}

minPrice is the minimum price from day 0 to day i. And maxPro is the maximum profit we can get from day 0 to day i.

How to get maxPro? Just get the larger one between current maxPro and prices[i] - minPrice.

https://discuss.leetcode.com/topic/5863/sharing-my-simple-and-clear-c-solution/5

Very nice solution! But it still can be optimized. We only need to calculate either maxProfit or minPrice not both in every loop. Running time can be dropped by 33% percent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProfit(int[] prices) {
if(prices == null || prices.length < 2) return 0;
int maxProfit = 0, minPrice = prices[0];

for(int i = 1; i < prices.length; i++) {
if(prices[i] > prices[i - 1]) {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
} else {
minPrice = Math.min(minPrice, prices[i]);
}
}

return maxProfit;
}

https://discuss.leetcode.com/topic/42716/5-line-cpp-solution

5 line CPP solution

1
2
3
4
5
6
7
8
int maxProfit(vector<int>& prices) {
int maxPro = 0, minPrice = INT_MAX;
for(int i = 0; i < prices.size(); i++) {
minPrice = min(minPrice, prices[i]);
maxPro = max(prices[i] - minPrice, maxPro);
}
return maxPro;
}

python


https://discuss.leetcode.com/topic/33241/easy-o-n-python-solution

Easy O(n) Python solution

1
2
3
4
5
6
7
def maxProfit(prices):
max_profit, min_price = 0, float('inf')
for price in prices:
min_price = min(min_price, price)
profit = price - min_price
max_profit = max(max_profit, profit)
return max_profit

java


Algorithm

Say the given array is:

[7, 1, 5, 3, 6, 4]

If we plot the numbers of the given array on a graph, we get:

image

The points of interest are the peaks and valleys in the given graph. We need to find the largest peak following the smallest valley. We can maintain two variables - minprice and maxprofit corresponding to the smallest valley and maximum profit (maximum difference between selling price and minprice) obtained so far respectively.

Complexity Analysis

  • Time complexity : O(n)O(n). Only a single pass is needed.

  • Space complexity : O(1)O(1). Only two variables are used.

针对每个点,与最小点比差值,如果最小点小于当前值,可以看其差值是否可以做最小值,如果最小点大于当前最小值,当前值可以作为最小值。

关键在于对每一个值遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int maxProfit(int[] prices) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for(int i=0; i<prices.length; i++){
if(prices[i]<minprice)
minprice = prices[i];
else if(prices[i] - minprice > maxprofit)
maxprofit = prices[i] - minprice;
}
return maxprofit;
}
}

my code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
public int maxProfit(int[] prices) {
if(prices.length<=1) return 0;
int valley=prices[0];
int maxprofit = 0;
for(int i=1; i<prices.length; i++){
if(prices[i-1]>prices[i])
valley = Math.min(valley, prices[i]);
else if(prices[i]-valley>maxprofit)
maxprofit = prices[i]-valley;
}
return maxprofit;
}
}

https://discuss.leetcode.com/topic/19853/kadane-s-algorithm-since-no-one-has-mentioned-about-this-so-far-in-case-if-interviewer-twists-the-input

The logic to solve this problem is same as “max subarray problem” using Kadane’s Algorithm. Since no body has mentioned this so far, I thought it’s a good thing for everybody to know.

All the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for {1, 7, 4, 11}, if he gives {0, 6, -3, 7}, you might end up being confused.

Here, the logic is to calculate the difference (maxCur += prices[i] - prices[i-1]) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.

  • maxCur = current maximum value

  • maxSoFar = maximum value found so far

1
2
3
4
5
6
7
8
public int maxProfit(int[] prices) {
int maxCur = 0, maxSoFar = 0;
for(int i = 1; i < prices.length; i++) {
maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
maxSoFar = Math.max(maxCur, maxSoFar);
}
return maxSoFar;
}

https://discuss.leetcode.com/topic/19853/kadane-s-algorithm-since-no-one-has-mentioned-about-this-so-far-in-case-if-interviewer-twists-the-input/2

Please refer to this for more details on the algorithm : https://en.wikipedia.org/wiki/Maximum_subarray_problem

谢谢你,可爱的朋友。