資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python求解方程最大值程式
假設我們有一個名為points的陣列，其中包含二維平面上的座標點，它們按x值排序，其中points[i] = (x_i, y_i)，因此對於所有1 <= i < j <= 點數，x_i < x_j。我們還有另一個值k。我們需要找到方程y_i + y_j + |x_i - x_j| 的最大值，其中|x_i - x_j| <= k 且 1 <= i < j <= 點數。
因此，如果輸入類似於 points = [[2,4],[3,1],[6,11],[7,-9]] k = 1，則輸出將為6，因為前兩個點滿足條件 |xi - xj| <= 1，如果我們計算方程，我們得到 4 + 1 + |2 - 3| = 6。第三個和第四個點也滿足條件，並返回 11 + -9 + |6 - 7| = 3 的值，所以最大值為6。
為了解決這個問題，我們將遵循以下步驟：
left := 0, right := 1
max_value := -∞
當 right < points 的大小 時，執行：
(xl, yl) := points[left]
(xr, yr) := points[right]
diff := |xr - xl|
如果 left 等於 right，則
right := right + 1
否則，如果 diff <= k，則
m := yl + yr + diff
max_value := max_value 和 m 的最大值
如果 yl >= yr - diff，則
right := right + 1
否則，
left := left + 1
否則，
left := left + 1
返回 max_value
示例
讓我們看看下面的實現來更好地理解
def solve(points, k):
left, right = 0, 1
max_value = float('-inf')
while right < len(points):
xl, yl = points[left]
xr, yr = points[right]
diff = abs(xr - xl)
if left == right:
right += 1
elif diff <= k:
m = yl + yr + diff
max_value = max(max_value, m)
if yl >= yr - diff:
right += 1
else:
left += 1
else:
left += 1
return max_value
points = [[2,4],[3,1],[6,11],[7,-9]]
k = 1
print(solve(points, k))輸入
[[2,4],[3,1],[6,11],[7,-9]], 1
輸出
6
更新於：2021年10月6日
441 次瀏覽
廣告