題目描述

給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

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

示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7

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

示例 2:
輸入: [1,2,3,4,5]
輸出: 4

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

示例 3:
輸入: [7,6,4,3,1]
輸出: 0

解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

數(shù)據(jù)結(jié)構(gòu)

• 數(shù)組

算法思維

• 遍歷、貪心
  
  

解題思路

一. Comprehend 理解題意

• 已知某個(gè)股票（整形數(shù)組）中的變化趨勢
• 進(jìn)行不限制次數(shù)的買入/賣出，使最終獲得的差價(jià)最大
  
  

二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法

貪心算法

• 數(shù)據(jù)結(jié)構(gòu)：數(shù)組
• 算法思維：遍歷、貪心
• 解題思路
  1）使用一個(gè)整型變量記錄 利潤
  2）如果 當(dāng)前值 - 上個(gè)值 > 0，則說明上個(gè)值買入、當(dāng)前值賣出是賺錢的，累加進(jìn) 利潤 中
  3）如果 當(dāng)前值 - 上個(gè)值 <0，則說明上個(gè)值買入、當(dāng)前值賣出使賠錢的，不累加（累加 0）
  4）返回 利潤
• 核心要點(diǎn)：
  1）最終得到的利潤值即為最大利潤，因?yàn)樘澅镜慕灰锥急惶蕹?，沒有被累加
  2）貪心思想體現(xiàn)在：當(dāng)前交易賺錢（當(dāng)前值 - 上個(gè)值 > 0）才納入累加，從而保證不虧錢
  
  

三. Code 編碼實(shí)現(xiàn)基本解法

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            profit += Math.max(0, prices[i] - prices[i - 1]);
        }
        return profit;
    }
}

執(zhí)行耗時(shí)：1 ms，擊敗了 99.47% 的Java用戶
內(nèi)存消耗：38.5 MB，擊敗了 18.11% 的Java用戶

時(shí)間復(fù)雜度：O(n)
? ? 數(shù)組的遍歷 O(n)

空間復(fù)雜度：O(1)
? ? 一個(gè)指針變量，占用常數(shù)級內(nèi)存空間 O(1)

四. Consider 思考更優(yōu)解

=== 待續(xù) ===

五. Code 編碼實(shí)現(xiàn)最優(yōu)解

=== 待續(xù) ===

六. Change 變形與延伸

=== 待續(xù) ==