有一個陣列 array 每一個元素代表的是該天股票的價格，i 代表的是天。
如果只允許您最多完成一筆交易（即買入和賣出一股股票），則設計一種算法以找到最大的利潤。
順帶一提，在你買股票之前是不能做賣股票的動作。
LeetCode 題目連結
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
題目
121. Best Time to Buy and Sell Stock
Easy
121. Best Time to Buy and Sell Stock
Easy
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 (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.
Accept 作法
這題我以為是真的要模擬真實買股票的狀況，畢竟股票怎可能知道最高點在哪邊？所以一開始我以為只要比較大獲得正報酬就賣出，其實不然，他還是要繼續找尋最大報酬。
Runtime: 307 ms
Memory: 41.8 MB
class Solution {
public int maxProfit(int[] prices) {
int lastEarnMoney = 0;
for(int i = 0; i< prices.length; i++){
for(int j = i+1; j < prices.length; j++){
if(prices[i] < prices[j]){
int result = prices[j] - prices[i];
if(lastEarnMoney < result){
lastEarnMoney = result;
}
}
}
}
return lastEarnMoney;
}
}
更多 LeetCode 相關資源
複習程式面試書籍
除了 LeetCode 練習外，我也入手了這本，題庫來自真正的面試，並非摘自教科書。它們反映出頂尖公司真正會出的題目，你可以藉此做好充分準備。
需要的話可以看看，寫得很仔細。
沒有留言:
張貼留言