Giả sử chúng ta có một danh sách các số được gọi là num và hai giá trị x và y, chúng ta phải tìm tổng lớn nhất của hai danh sách con không trùng nhau trong nums có độ dài x và y.
Vì vậy, nếu đầu vào là nums =[3, 2, 10, -2, 7, 6] x =3 y =1, thì đầu ra sẽ là 22, vì danh sách con có độ dài 3, chúng tôi chọn [3, 2, 10] và đối với cái khác, chúng tôi chọn [7].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- P:=một danh sách có một phần tử 0
- với mỗi x trong A, thực hiện
- chèn (phần tử cuối cùng của P + x) vào cuối P
- Xác định một hàm giải quyết (). Thao tác này sẽ lấy len1, len2
- Q:=một danh sách có phần tử (P [i + len1] - P [i]) cho mỗi i trong phạm vi từ 0 đến kích thước là P - len1
- tiền tố:=bản sao của Q
- đối với tôi trong phạm vi từ 0 đến kích thước của tiền tố - 1, thực hiện
- tiền tố [i + 1]:=tối đa tiền tố [i + 1] và tiền tố [i]
- ans:=-infinity
- for i in range len1 to size of P - len2, do
- left:=prefix [i - len1]
- đúng:=P [i + len2] - P [i]
- ans:=tối đa ans và (trái + phải)
- trả lại ans
- Từ phương thức chính, hãy làm như sau -
- trả về giá trị tối đa của giải quyết (len1, len2), giải quyết (len2, len1)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution:
def solve(self, A, len1, len2):
P = [0]
for x in A:
P.append(P[-1] + x)
def solve(len1, len2):
Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]
prefix = Q[:]
for i in range(len(prefix) - 1):
prefix[i + 1] = max(prefix[i + 1], prefix[i])
ans = float("-inf")
for i in range(len1, len(P) - len2):
left = prefix[i - len1]
right = P[i + len2] - P[i]
ans = max(ans, left + right)
return ans
return max(solve(len1, len2), solve(len2, len1))
ob = Solution()
nums = [3, 2, 10, -2, 7, 6]
x = 3
y = 1
print(ob.solve(nums, x, y)) Đầu vào
[3, 2, 10, -2, 7, 6], 3, 1
Đầu ra
22