這題是一個經典的動態規劃問題,目標是找到一個陣列中連續子陣列的合還有回傳最大值,時間複雜度可達 O(n)
,這裡有 JAVA 和 Python 的寫法。
Given an integer array
nums
, find the subarray with the largest sum, and return its sum.
給定一個整數陣列
nums
,找到最大總合的子陣列,然後回傳子陣列的總合。
題目連結:https://leetcode.com/problems/maximum-subarray/
1 <= nums.length <= 105
104 <= nums[i] <= 104
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
直觀的做法是把元素依依累加下去,這也代表為連續的子陣列,然後再將這個子陣列相加的最大數存起來。
- 遍歷索引累加下去,子陣列的合會越來越大,代表此子陣列的合上限一直在增加。(這樣可以確保當前子陣列的總合是連續的,且是最大的值)
- 再來比較子陣列的合跟最大值,更新到最大的值。
- 後續要判斷相加的合如果小於 0 的話,重新找子陣列的起點,再依依累加下去。
- 因為子陣列的合為負數,表示對後續的合沒有貢獻,將其重置為 0。(假如是負數的話對於子陣列的合會被扣掉)
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length; // 陣列的長度
int max = Integer.MIN_VALUE; // 確保整數為最小值 (有可能比0還要小)
int sum = 0; // 子陣列的合
for(int i=0;i<n;i++){
sum += nums[i]; // 子陣列的合 + 當下索引的值
max = Math.max(sum,max); // 子陣列的合、最大值,取比較大的數
if(sum<0) {
sum = 0; // 子陣列的合重製為 0
}
}
return max; // 回傳最大值
}
}
使用了和 Java 一樣的邏輯執行,換成 Python 的寫法。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums) # 陣列長度
current_sum = 0 # 子陣列的合
current_max = float('-inf') # 確保是最小的整數
for i in range(n):
current_sum += nums[i] # 子陣列的合 + 當下索引的值
current_max = max(current_sum, current_max) # 子陣列的合、最大值,取比較大的數
if (current_sum<0):
current_sum = 0 # 子陣列的合重製為 0
return current_max # 回傳最大數
Language | Runtime | Memory |
---|---|---|
Java | 1ms | 59.1MB |
Python | 719ms | 30.6MB |
(新手上路,如有錯誤請友善告知,感謝)
Blog
https://chris81051.github.io/2023/05/31/LeetCode-53-Maximum-Subarray-Java-Python/
有分享技術文章、科技新聞、日常生活,歡迎一起討論