# Best Time to Buy and Sell Stock

• We need to find out the maximum difference (which will be the maximum profit) between two numbers in the given array. Also, the second number (selling price) must be larger than the first one (buying price).

• has the first approach consider j>i?

• I am not sure why Zero is considered as the valid value is array for selling or buying stocks.Few of my test cases are failing because of this.For e.g. : [2,1,2,1,0,1,2]

• mark :) I am here

• Is Approach #2 a dp approach?

• First time been here

• I really dont think the approach #2 is a DP approach...

• Approach 2: Greedy approach

• int maxProfit(int* prices, int pricesSize) {
if (NULL == prices || pricesSize <= 0)
return  0;

int minPrice = prices[0];
int max_profit = 0, i = 0;

for(i = 1; i < pricesSize; i ++)
{
int tmpProfit = prices[i] - minPrice;

if (prices[i] < minPrice)
{
minPrice = prices[i];
}

if ((max_profit < tmpProfit))
{
max_profit = tmpProfit;
}
}

return max_profit;
}

• Slightly more simpler

public int maxProfit(int[] prices) {
int maxPrice = 0;
int profit = 0;
for (int i = prices.length - 1 ; i >= 0 ; i--) {
profit = Math.max(maxPrice - prices[i], profit);
maxPrice = Math.max(maxPrice, prices[i]);
}
return profit;
}

• class Solution(object):
def maxProfit(self, prices):

sol = list()
for index, value in enumerate(prices):
starting=prices[:index+1]
ending=prices[index+1:]
if starting and ending:
value = max(ending)-min(starting)
sol.append(value)
if sol:
j=max(sol)
if j>0:
return (max(sol))
else:
return 0
else:
return 0

• Condition about selling and buying is not exactly clear. It means that you must buy as a first operation and only then sell? Correct?
So, it means you don't have stocks before these operations, so you can't sell, then buy?

• Why not just use Math.min/max?

maxprofit = Math.max(maxprofit, prices[i] - minprice);
minprice = Math.min(minprice, prices[i]);

• I dont think the approach #2 is a DP approach

• AH. I thought again and again and found out dp could not complete this problem with time complexity less than O(n ^ 2). Guess what, this solution is greedy instead of dp.

• O(n) solution using heapq in python

import heapq

class Solution(object):
def maxProfit(self, prices):
pheap=[]
maxprofit=0

for price_i in prices:
if not pheap:
heapq.heappush(pheap,price_i)
elif price_i-pheap[0]>maxprofit:
maxprofit= price_i-pheap[0]
heapq.heappush(pheap,price_i)
return maxprofit

• /*
利用动态规划，从后往前遍历解决
*/

class Solution {
public int maxProfit(int[] prices) {
int max;
int l = prices.length;
if(l == 0 || l == 1){
return 0;
}
int[] d = new int[l];
d[l-2] = prices[l-1] - prices[l-2];
max = d[l-2];
for(int i = l -3; i >= 0; i--){
d[i] = ((prices[i+1] > d[i+1]+prices[i+1]) ? prices[i+1] : d[i+1]+prices[i+1]) - prices[i];
if(max < d[i]){
max = d[i];
}
}
if(max < 0)
return 0;
return max;
}
}

• '''
/*
利用动态规划，从后往前遍历解决
*/

class Solution {
public int maxProfit(int[] prices) {
int max;
int l = prices.length;
if(l == 0 || l == 1){
return 0;
}
int[] d = new int[l];
d[l-2] = prices[l-1] - prices[l-2];
max = d[l-2];
for(int i = l -3; i >= 0; i--){
d[i] = ((prices[i+1] > d[i+1]+prices[i+1]) ? prices[i+1] : d[i+1]+prices[i+1]) - prices[i];
if(max < d[i]){
max = d[i];
}
}
if(max < 0)
return 0;
return max;
}
}
'''

• static int oneMaxProfit(int arr[]){
int minPrice=Integer.MAX_VALUE;int maxPrice=Integer.MIN_VALUE; int profit=0;
//minPrice=arr[0];
for(int i=0;i<arr.length;i++){
if(arr[i]<minPrice) minPrice=arr[i];
if(arr[i]>maxPrice) maxPrice=arr[i];
else maxPrice=minPrice; //Max Price only after i
profit=Math.max(profit, maxPrice-minPrice);
//System.out.println(i +" "+minPrice+" "+maxPrice+" "+profit);
}
return profit;
}

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