Giả sử, chúng ta được cung cấp một mảng chứa các số nguyên. Chúng ta có thể thực hiện một phép toán trong đó chúng ta có thể thay thế giá trị của mảng [i] bằng giá trị bình phương của nó; hoặc mảng [i] * mảng [i]. Chỉ cho phép một thao tác thuộc loại này và chúng ta phải trả về tổng của mảng con tối đa có thể sau thao tác này. Mảng con không được để trống.
Vì vậy, nếu đầu vào giống như mảng =[4, 1, -2, -1], thì đầu ra sẽ là 17.
Nếu chúng ta thay thế giá trị trong mảng [0] bằng giá trị bình phương của nó, mảng sẽ trở thành [16, 1, -2, -1]. Mảng con tối đa có thể có từ này là [16, 1] và nó có tổng giá trị lớn nhất là 16 + 1 =17.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- dp1:=một danh sách mới chứa giá trị âm vô cùng
- dp2:=một danh sách mới chứa giá trị âm vô cùng
- đối với mỗi num trong mảng, thực hiện
- chèn tối đa ((phần tử cuối cùng của dp1 + num), num) vào cuối dp1
- chèn tối đa ((phần tử cuối cùng thứ hai của dp1 + num ^ 2), num ^ 2, (phần tử cuối cùng của dp2 + num)) vào cuối dp2
- trả về phần tử tối đa của dp2
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(array):
dp1 = [float('-inf')]
dp2 = [float('-inf')]
for num in array:
dp1.append(max(dp1[-1] + num, num))
dp2.append(max(dp1[-2] + num**2, num**2, dp2[-1]+num))
return max(dp2)
print(solve([4, 1, -2, -1])) Đầu vào
[4, 1, -2, -1]
Đầu ra
17