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.
Example 1:
Input: [7, 1, 5, 3, 6, 4]Output: 5max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
Input: [7, 6, 4, 3, 1]Output: 0In this case, no transaction is done, i.e. max profit = 0.
Subscribe to see which companies asked this question.
題目
假設(shè)有一個(gè)數(shù)組乏梁，它的第i個(gè)元素是一支給定的股票在第i天的價(jià)格抱慌。如果你最多只允許完成一次交易(例如,一次買賣股票),設(shè)計(jì)一個(gè)算法來找出最大利潤胀瞪。
樣例
給出一個(gè)數(shù)組樣例 [3,2,3,1,2], 返回 1
Solution
Approach #1 (Brute Force) 暴力搜索
思路很簡單发钝，我們就要找出數(shù)組中，差值最大的兩個(gè)數(shù)，要求是前一個(gè)數(shù)小，后一個(gè)數(shù)大洲愤，那么遍歷兩邊即可，找出所有這樣的差值漱竖，找出其中最大的一個(gè)
public int maxProfit(int prices[]) {
int maxprofit = 0;
for (int i = 0; i < prices.length - 1; i++) {
for (int j = i + 1; j < prices.length; j++) {
int profit = prices[j] - prices[i];
if (profit > maxprofit)
maxprofit = profit;
}
}
return maxprofit;
}
Approach #2 (One Pass) Greedy 貪婪法
通過一遍遍歷禽篱，找出到此為止之前最小的min,并與當(dāng)前的值求差，保存最大的差值馍惹，遍歷完躺率，最后的差值即是最大差值玛界。
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;
}
