สมมติว่าเรามีอาร์เรย์ A ในที่นี้ A[i] จะแสดงราคาของหุ้นที่กำหนดในวันที่ i เราต้องหากำไรสูงสุด เราสามารถดำเนินการได้มากสุดหนึ่งรายการ (ธุรกรรมหมายถึงการซื้อและขายหุ้น) แต่เราต้องจำไว้ว่าเราอาจไม่ได้ทำธุรกรรมหลายรายการพร้อมกัน จึงต้องขายหุ้นก่อนซื้อใหม่ครับ
สมมติว่าอาร์เรย์เป็นเหมือน A =[7, 1, 5, 3, 6, 4] แล้วผลลัพธ์จะเป็น 5 อย่างที่เห็น หากเราซื้อในวันที่ 2 (ดัชนี 1) ก็จะได้ 1 เป็น ราคาซื้อ แล้วถ้าเราขายในวันที่ 5 กำไรจะเป็น 6 – 1 =5.
ในการแก้ปัญหานี้ ให้ทำตามขั้นตอนเหล่านี้ -
- สร้างสองอาร์เรย์ leftMin และ rightMax ของขนาดเดียวกับ A และเติมด้วย 0s
- 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]
- กำหนดคำตอบ :=0
- สำหรับฉันในช่วง 0 ถึงความยาวของ A – 1 ตอบ :=สูงสุดของคำตอบและ rightMax[i + 1] – leftMin[i]
- ส่งคืนคำตอบ
มาดูการใช้งานกันให้เกิดความเข้าใจกันมากขึ้น
ตัวอย่าง
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]) #print(leftMin) rightMax[-1]= prices[-1] for i in range(len(prices)-2,-1,-1): rightMax[i] = max(rightMax[i+1],prices[i]) #print(rightMax) 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
