Best Time to Buy and Sell Stock (E)
題目
Say you have an array for which the \(i^{th}\) element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 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
Explanation: In this case, no transaction is done, i.e. max profit = 0.
題意
找到陣列中兩個數的最大差，注意較小數需要排在較大數之前，
思路
使用類似動態規劃的方法：從左向右遍歷陣列，記錄leftMin為以當前下標為右邊界的左子陣列中的最小值，每次判斷更新leftMin，并判斷當前值減去leftMin是否大于最大利潤，是則更新最大利潤，與動態規劃的區別在于不需要另開陣列記錄每一個下標對應的leftMin，
代碼實作
Java
class Solution {
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int leftMin = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] < leftMin) {
leftMin = prices[i];
} else if (prices[i] - leftMin > maxProfit) {
maxProfit = prices[i] - leftMin;
}
}
return maxProfit;
}
}
JavaScript
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function (prices) {
let leftMin = prices[0]
let maxProfit = 0
for (let i = 1; i < prices.length; i++) {
maxProfit = Math.max(maxProfit, prices[i] - leftMin)
leftMin = Math.min(leftMin, prices[i])
}
return maxProfit
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/76778.html
標籤：其他