iT邦幫忙

0

[LeetCode 筆記] 53. Maximum Subarray

  • 分享至 

  • xImage
  •  

前言

  這題是一個經典的動態規劃問題,目標是找到一個陣列中連續子陣列的合還有回傳最大值,時間複雜度可達 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。(假如是負數的話對於子陣列的合會被扣掉)

JAVA 實現

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; // 回傳最大值
    }
}

Python 實現

使用了和 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/
有分享技術文章、科技新聞、日常生活,歡迎一起討論


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言