動機
- 列舉十分可怕
- 不要拘泥於題目
- 新看法: 把資料畫成座標圖
Problem
You are given an array prices where prices[i] is the price of a given stock on the ith day.
Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1:
Input: prices = [7,1,5,3,6,4]Output: 7Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
Input: prices = [1,2,3,4,5]Output: 4Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: prices = [7,6,4,3,1]Output: 0Explanation: In this case, no transaction is done, i.e., max profit = 0.
Constraints:
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104
Sol1: TLE
因為可以無限次，又要買高賣低，所以就用列舉去找
class Solution:
def num1(self, ps):
ans = 0
lowest_price = ps[0]
for x in range(0, len(ps)):
lowest_price = min([lowest_price, ps[x]])
ans = max([ans, ps[x] - lowest_price])
return ans
@functools.cache
def f(self, i, j):
ret = 0
if i == j:
ret = 0
elif j - i == 1:
ret = max(0, self.ps[j] - self.ps[i])
elif j - i == 2: # What!?
ret = max(0, self.num1(
self.ps[i:j+1]), self.ps[j] - min(self.ps[i], self.ps[i+1]))
else:
ret = max([self.f(i, k) + self.f(k + 1, j) for k in range(i + 1, j)])
ret = max(ret, self.num1(self.ps[i:j+1]))
#print("at ", i, j, ret)
return ret
def maxProfit(self, prices: List[int]) -> int:
self.ps = prices
return self.f(0, len(prices)-1)
Sol2: AC
- 從最低到最高的距離，與這之間點與點之間的間隔的加總是一樣的!!
例
1, 3, 4, 7
7-1 = 6
3-1 + 4-3 + 7-4 = 6
- 買了就一定要賣掉才能買 <= 不用特別等!!
所以，只要把所有利潤加起來就好，除了會覆蓋到最地道最高的case還有，還有中間震盪的case
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
for i in range(0,len(prices)-1):
if prices[i] < prices[i+1]:
ans += prices[i+1]-prices[i]
return ans