[LeetCode] 53. Maximum Subarray

前言

　　這題是一個經典的動態規劃問題，目標是找到一個陣列中連續子陣列的合還有回傳最大值，時間複雜度可達 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

範例

1
2
3

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.

1
2
3

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

1
2
3

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