資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚
法學Python 中的最大子陣列
假設我們有一個整數陣列 A。我們必須找出長度至少為 1 的連續子陣列，並且其和最大，並返回其和。因此，如果陣列 A 類似於 A = [-2,1,-3,4,-1,2,1,-5,4]，則總和為 6。子陣列將為 [4, -1, 2, 1]
為了解決這個問題，我們將嘗試使用動態規劃方法。
- 定義一個數組 dp 與 A 的大小相同，並將其填充為 0
- dp[0] := A[0]
- 對於 i 從 1 到 A 的大小 - 1
- dp[i] := dp[i – 1] + A[i] 和 A[i] 的最大值
- 返回 dp 中的最大值
讓我們看看以下實現以獲得更好的理解 -
示例（Python）
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ dp = [0 for i in range(len(nums))] dp[0] = nums[0] for i in range(1,len(nums)): dp[i] = max(dp[i-1]+nums[i],nums[i]) #print(dp) return max(dp) nums = [-2,1,-3,7,-2,2,1,-5,4] ob1 = Solution() print(ob1.maxSubArray(nums))
輸入
nums = [-2,1,-3,7,-2,2,1,-5,4]
輸出
8
更新於：28-4-2020
4K+ 瀏覽
廣告