【刷算法】LeetCode.150-買賣股票的最佳時機 II

Vultr 發布于2019-08-23 11:45 / 2846人閱讀

摘要：題目描述給定一個數組，它的第個元素是一支給定股票第天的價格。設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易多次買賣一支股票。隨后，在第天股票價格的時候買入，在第天股票價格的時候賣出這筆交易所能獲得利潤。

題目描述

給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。

設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:

輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
     隨后，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

示例 2:

輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。
     因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。

示例 3:

輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

代碼實現

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {
    if(prices === null || prices.length === 0 || prices.length === 1)
        return 0;

    let index = 0;
    let res = 0;    

    for(let i = 0;i < prices.length-1;i++) {
        if(prices[i+1] <= prices[i]) {
            res += (prices[i] - prices[index]);
            index = i+1;
        }
    }
    
    if(index !== prices.length-1 && prices[prices.length-1] > prices[index])
        res += prices[prices.length-1] - prices[index];
    return res;
};

云服務器 GPU云服務器最佳置換算法的實現最佳的抗鋸齒算法最佳頁面置換算法的歷史最佳適應算法的空閑分區是

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/97415.html

【LeetCode】貪心算法--買賣股票的最佳時機 II（122）

摘要：貪心算法每一步必須滿足一下條件可行的即它必須滿足問題的約束。四題目分析貪心算法，總是做出在當前看來是最好的選擇，不從整體最優上加以考慮，也就是說，只關心當前最優解，按照貪心策略，不關心以后，我們只關心當前利益。一、寫在前面為什么要在LeetCode刷題？大家都知道不管是校招還是社招算法題是必考題，而這一部分恰巧是大多數人的短板，所以刷題首先是為了提高自身的編程能力，能夠在算法面試中...

xbynet 2019-07-31 11:21 評論0 收藏0
大廠算法面試之leetcode精講3.動態規劃

摘要：動態規劃問題一定會具備最優子結構，才能通過子問題的最值得到原問題的最值。另外，雖然動態規劃的核心思想就是窮舉求最值，但是問題可以千變萬化，窮舉所有可行解其實并不是一件容易的事，只有列出正確的狀態轉移方程才能正確地窮舉。大廠算法面試之leetcode精講3.動態規劃視頻教程（高效學習）:點擊學習目錄：1.開篇介...

番茄西紅柿 2021-11-22 14:56 評論0 收藏2637
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
Best Time To Buy And Sell Stock 買賣股票最佳時機

摘要：關鍵字，，算法，，動態規劃，上關于主題的題目有四個這四個題目難度依次遞增。其中第四個問題是尋求一個通解，在給定和最大買賣次數的情況下，求最大收益。首先大致的解題方向是動態規劃，這個應該不難想到。之后就是怎么找到狀態，怎么列狀態轉移方程。關鍵字：leetcode，Best Time To Buy And Sell Stock，算法，algorithm，動態規劃，dynamic prog...

elliott_hu 2019-08-15 15:40 評論0 收藏0
前端也需要好好的精進自己的算法

摘要：算法前端發展的再快，也不要忘記精進自己的算法，算法是靈魂和核心。我會把我刷過的算法題總結歸類，不斷完善。算法前端發展的再快，也不要忘記精進自己的算法，算法是靈魂和核心。我會把我刷過的算法題總結歸類，不斷完善。歡迎大家關注。數組和堆棧數組去重旋轉數組如何快速找出兩個數之和等于某一個值的兩個數？快排排序算法大總結快速找到數組中的最大值多維數組的展開二分查找有效的括...

hersion 2019-08-23 10:36 評論0 收藏0