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.
[Thought]
Using greedy algorithm to solve this problem . Scan from left to right , and keep track the minimum price . If the difference between the minimum value and price is bigger than the profit , replace it.
public class Solution {
public int maxProfit(int[] prices) {
if(prices.length == 0)
return 0;
int profit = 0;
int min = prices[0];
for(int i=0;i<prices.length;i++){
if(prices[i]<min){
min = prices[i];//keep track the minimum value
}else{
if(prices[i] - min > profit){//if the difference between price[i] and minimum price is bigger than profit , replace it.
profit = prices[i]-min;
}
}
}
return profit;
}
}