Leetcode :: Maximum Subarray

Problems

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Guess

• 당장 떠오르는건 Brute force.
• 그러나 Kadane algorithm을 이용하면 O(n) 복잡도로 해결할 수 있다.

Solution

 class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        for i in range(1,len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
                
        return max(nums)