สมมติว่าเรามีอาร์เรย์ A ที่ A[i] แสดงราคาหุ้นในวันที่ i เราต้องหากำไรสูงสุด เราสามารถทำธุรกรรมได้สูงสุดหนึ่งครั้ง (ธุรกรรมหมายถึงซื้อและขายหุ้น) แต่ต้องจำว่าไม่สามารถทำธุรกรรมหลายอย่างพร้อมกันได้ ต้องขายหุ้นก่อนจึงจะซื้อใหม่ได้
สมมติอาร์เรย์เป็น A = [7, 1, 5, 3, 6, 4] ผลลัพธ์จะเป็น 5 เราสามารถเห็นได้ว่าถ้าซื้อวันที่ 2 (ดัชนี 1) ราคาซื้อ 1 แล้วขายวันที่ 5 กำไร 6 - 1 = 5
วิธีการแก้ปัญหา
- สร้างอาร์เรย์สองอัน leftMin และ rightMax ขนาดเท่ากับ A และเติมด้วย 0
- leftMin[0] = A[0]
- สำหรับ i ในช่วง 1 ถึงความยาวของ A - 1, leftMin[i] = ค่าต่ำสุดของ leftMin[i - 1] และ A[i]
- rightMax[n-1] = A[n - 1]
- สำหรับ i ในช่วงความยาวของ A - 1 ลงถึง 1, rightMax[i] = ค่าสูงสุดของ rightMax[i + 1] และ A[i]
- ตั้งค่า answer := 0
- สำหรับ i ในช่วง 0 ถึงความยาวของ A - 1, answer := ค่าสูงสุดของ answer และ rightMax[i + 1] - leftMin[i]
- คืนค่า answer
ตัวอย่าง
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices:
return 0
leftMin, rightMax = [0 for i in range(len(prices))], [0 for i in range(len(prices))]
leftMin[0] = prices[0]
for i in range(1, len(prices)):
leftMin[i] = min(leftMin[i-1], prices[i])
rightMax[-1] = prices[-1]
for i in range(len(prices)-2, -1, -1):
rightMax[i] = max(rightMax[i+1], prices[i])
ans = 0
for i in range(len(prices)-1):
ans = max(ans, rightMax[i+1] - leftMin[i])
return ans
ob1 = Solution()
print(ob1.maxProfit([7,2,5,8,6,3,1,4,5,4,7]))
อินพุต
prices = [7,2,5,8,6,3,1,4,5,4,7]
เอาต์พุต
6
