主題
Description:
給定一個數列nums，依序找到i , j, k(i < j < k)，使得(nums[i]-nums[j]) * nums[k]最大，若為負值則回傳0
思考：
# 乘數越大越好?
# 一個區間內減法最大的兩數
# i < j < k，這能不能來幫忙思考
# GPT: 以j為中心去思考，找[0, j-1]最大的i，[j+1, k]最大的k
那就，先找到最小的j，然後從他那邊開始找左右
mid = min(nums[1:len(nums)-1]) # len(nums) >= 3
j = nums.index(mid)
return max(0, (max(nums[0:j]) - mid) * (max(nums[j+1:len(nums)])))
但這樣不一定會找到最小的
ex: [8,6,3,13,2,12,19,5,19,6,10,11,9]，會找到13,2,19，但19,5,19更大
=====
Prefix跟Sufix這個主題我也很弱呢，可以多練
正在校正身體的時間
今天要更早睡一點，起床頭有點痛
class Solution:
def maximumTripletValue(self, nums: List[int]) -> int:
n = len(nums)
# Step 1: build prefix max
prefix_max = [0] * n
prefix_max[0] = nums[0]
for i in range(1,n):
prefix_max[i] = max(prefix_max[i-1], nums[i])
# Step 2: build suffix max
suffix_max = [0] * n
suffix_max[-1] = nums[-1]
for i in range(n-2, -1, -1):
suffix_max[i] = max(suffix_max[i+1], nums[i])
# Step 3: try each j
max_value = 0
for j in range(1, n-1):
left = prefix_max[j-1]
right = suffix_max[j+1]
value = (left - nums[j]) * right
max_value = max(max_value, value)
return max_value
