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).
Click here to see the full article post
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).
Click here to see the full article post
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;
}
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
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;
}