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.
Solution:
The key is to understand this question.
1. It assumes that we have unlimited amount of money enables us to buy any stock
2. The profit is equal to sell price - buy price, so we want a min buy price and a max sell price, under the condition of selling before buying.
Solution:
The key is to understand this question.
1. It assumes that we have unlimited amount of money enables us to buy any stock
2. The profit is equal to sell price - buy price, so we want a min buy price and a max sell price, under the condition of selling before buying.
public class Solution {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int maxDiff = 0;
for(int i = 0; i < prices.length; i++){
if(prices[i] < min) min = prices[i];
if(prices[i] - min > maxDiff) maxDiff = prices[i] - min;
}
return maxDiff;
}
}
No comments:
Post a Comment