資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：求操作後最大子陣列的和
假設我們有一個包含整數的陣列。我們可以執行一個操作，將陣列中`array[i]`的值替換為其平方值；或者`array[i] * array[i]`。只允許進行一次這樣的操作，我們必須返回操作後最大可能子陣列的和。子陣列不能為空。
因此，如果輸入類似於`array = [4, 1, -2, -1]`，則輸出將為17。
如果我們將`array[0]`的值替換為其平方值，則陣列變為`[16, 1, -2, -1]`。由此可以得到最大子陣列是`[16, 1]`，其最大和值為16 + 1 = 17。
為了解決這個問題，我們將遵循以下步驟：
- dp1 := 一個新列表，包含負無窮大的值
- dp2 := 一個新列表，包含負無窮大的值
- 對於陣列中的每個數字，執行以下操作：
- 在dp1的末尾插入`max((dp1的最後一個元素 + num), num)`
- 在dp2的末尾插入`max((dp1的倒數第二個元素 + num^2), num^2, (dp2的最後一個元素 + num))`
- 返回dp2中的最大元素
示例
讓我們看看下面的實現，以便更好地理解：
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]))輸入
[4, 1, -2, -1]
輸出
17
更新於：2021年10月7日
141 次瀏覽
廣告