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: 5
max. 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: 0
In this case, no transaction is done, i.e. max profit = 0.
這道題比較笨的方式是O(n^2)，全都比一遍惦银，這里做了一點(diǎn)小小的優(yōu)化咆课，就是如果一個數(shù)比它的下一個大，那這個數(shù)肯定不會是買入點(diǎn)扯俱。
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
var profit = 0;
var days = prices.length;
for (var i = 0; i < days; i++) {
if (prices[i]>prices[i+1]) {
continue;
}
for (var j = i+1; j<days;j++) {
var tamp = prices[j]-prices[i];
if (tamp>profit)
profit = tamp;
}
}
return profit;
};
還有一種辦法书蚪，只走一遍，在走的過程中把到目前為止最小的記錄下來迅栅，并用當(dāng)前的減去最小的殊校，得到的值中最大的就是最大利潤。
var maxProfit = function(prices) {
// var profit = 0;
// var days = prices.length;
// for (var i = 0; i < days; i++) {
// if (prices[i]>prices[i+1]) {
// continue;
// }
// for (var j = i+1; j<days;j++) {
// var tamp = prices[j]-prices[i];
// if (tamp>profit)
// profit = tamp;
// }
// }
// return profit;
var minprice = prices[0];
var maxprofit = 0;
var num = prices.length;
for (var i = 0; i<num; i++){
if (prices[i]<minprice)
minprice = prices[i];
if ((prices[i]-minprice)>maxprofit) {
maxprofit = prices[i]-minprice;
}
}
return maxprofit;
};
