Leetcode 53. Maximum Subarray

給一個整數陣列nums，找出這個陣列中最大連續數的總和是多少(至少包含一個數)，題目希望時間複雜度為O(n)

Python

解法一 :

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums)==0 : return 0
        sum,max_val=nums[0],nums[0]
        for i in range(1,len(nums)):       
            if nums[i]>sum and sum<0:     #陣列元素比sum還大，sum是負數
                sum=nums[i]               #這個元素值為新的sum
            else:
                sum+=nums[i]              #累加sum
            max_val=max(sum,max_val)
        return max_val

解法二 :

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = cur = nums[0]
        for n in nums[1:]:
            cur = max(cur + n, n)       #自己加上下一個數跟下一個數比大小
            res = max(res, cur)         #儲存sum結果互比大小
        return res

解法三 :

class Solution(object):
    def maxSubArray(self, nums):
        res=nums[0]
        for i in range(1,len(nums)):
            if nums[i-1]>0:          #如果前一個數合大於0，跟目前的數相加
                nums[i]=nums[i]+nums[i-1]
            res=max(res,nums[i])
        return res

C++

動態規劃（Dynamic Programming）：

算法思路：

定義一個變量 maxSum 和 currSum，其中 maxSum 記錄整個數組的最大子數組和，currSum 記錄以當前位置為結尾的最大子數組和；
遍歷整個數組，如果 currSum 加上當前數值大於當前數值本身，則說明最大子數組和可以包含當前數值，因此 currSum 更新為 currSum + nums[i]；
如果 currSum 加上當前數值小於當前數值本身，則說明最大子數組和不包含當前數值，因此 currSum 更新為 nums[i]；
每次更新 currSum 後，比較 maxSum 和 currSum，將較大的值賦給 maxSum；
遍歷結束後，返回 maxSum。

時間複雜度為 O(n)，空間複雜度為 O(1)。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int maxSum = nums[0], currSum = nums[0];

        for(int i = 1; i < n; i++){
            currSum = max(nums[i], currSum + nums[i]);
            maxSum = max(maxSum, currSum);
        }
        return maxSum;
    }
};

Python

C++

相關