本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3572. 选择不同 X 值三元组使 Y 值之和最大 - 力扣（LeetCode）
解题思路
哈希表记录最值，当不同元素个数小于 3 返回-1，不然返回前三大的值之和
示例代码
python
class Solution:
def maxSumDistinctTriplet(self, x: List[int], y: List[int]) -> int:
d = defaultdict(int)
for a, b in zip(x, y):
d[a] = max(d[a], b)
return sum(sorted(d.values())[-3:]) if len(d) >= 3 else -13573. 买卖股票的最佳时机 V
解题思路
状态机 DP，交易结束，普通交易买入，做空交易卖出
示例代码
python
class Solution:
def maximumProfit(self, prices: List[int], k: int) -> int:
n = len(prices)
f = [[[0, -inf, -inf] for _ in range(k + 1)] for _ in range(n + 1)]
for t in range(k + 1):
for i in range(n):
f[i + 1][t][1] = max(f[i][t][1], f[i][t][0] - prices[i])
f[i + 1][t][2] = max(f[i][t][2], f[i][t][0] + prices[i])
f[i + 1][t][0] = max(f[i][t][0], f[i][t - 1][1] + prices[i], f[i][t - 1][2] - prices[i])
return f[n][k][0]python
class Solution:
def maximumProfit(self, prices: List[int], k: int) -> int:
n = len(prices)
f = [[0] * (k + 1) for _ in range(n + 1)]
for t in range(1, k + 1):
mx1 = mx2 = -inf
for i in range(n):
mx1 = max(mx1, f[i][t - 1] - prices[i])
mx2 = max(mx2, f[i][t - 1] + prices[i])
f[i + 1][t] = max(f[i][t], mx1 + prices[i], mx2 - prices[i])
return f[n][0]python
class Solution:
def maximumProfit(self, prices: List[int], k: int) -> int:
f = [[0, -inf, -inf] for _ in range(k + 2)]
f[0][0] = -inf
for p in prices:
for j in range(k + 1, 0, -1):
f[j][0] = max(f[j][0], f[j][1] + p, f[j][2] - p)
f[j][1] = max(f[j][1], f[j - 1][0] - p)
f[j][2] = max(f[j][2], f[j - 1][0] + p)
return f[k + 1][0]3574. 最大子数组 GCD 分数 - 力扣（LeetCode）
解题思路
示例代码
python
class Solution:
def maxGCDScore(self, nums: List[int], k: int) -> int:
n = len(nums)
ans = 0
for i in range(n):
c = 0
g = nums[i]
for j in range(i, -1, -1):
ng = gcd(g, nums[j])
if g // ng % 2 == 0:
c = i - j
elif nums[j] // ng % 2 == 0:
c += 1
g = ng
l = i - j + 1
ans = max(ans, g * l)
if k >= l - c:
ans = max(ans, g * l * 2)
elif g * (i + 1) < ans:
break
return anspython
class Solution:
def maxGCDScore(self, nums: List[int], k: int) -> int:
n = len(nums)
ans = 0
for i in range(n):
c = k
g = nums[i] << 1 if c else nums[i]
h = []
for j in range(i, -1, -1):
x = nums[j]
if c:
x <<= 1
lowbit = x & -x
g = gcd(g, x)
heappush(h, -lowbit)
c -= 1
else:
g = gcd(g, x)
l = i - j + 1
if g * l > ans:
ans = g * l
elif g * (i + 1) < ans:
break
lowbit = g & -g
while h and -h[0] > lowbit:
heappop(h)
c += 1
return anspython
class Solution:
def maxGCDScore(self, nums: List[int], k: int) -> int:
n = len(nums)
ans = 0
for i in range(n):
g = lb_cnt = 0
lb_min = inf
for j in range(i, -1, -1):
x = nums[j]
lb = x & -x
if lb < lb_min:
lb_min, lb_cnt = lb, 1
elif lb == lb_min:
lb_cnt += 1
g = gcd(g, x)
ng = g << 1 if lb_cnt <= k else g
if ng * (i - j + 1) > ans:
ans = ng * (i - j + 1)
elif ng * (i + 1) < ans:
break
return ans3575. 最大好子树分数 - 力扣（LeetCode）
解题思路
参考：这道题很神秘，以后再来解决吧！
示例代码
python
TODO