Leet code 53 - Maximum Subarray

 

---

브루트포스를 활용한 풀이 내풀이

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        sum1 = -100000
        max_num = -100000

        if len(nums) ==1:
            return nums[0]

        for i in range(len(nums)):
            sum1 = nums[i]
            if sum1 > max_num:
                max_num = sum1

            for j in range(i+1,len(nums)):
                sum1 += nums[j]
            
                if sum1 > max_num:
                    max_num = sum1
            
            if sum1 > max_num:
                max_num = sum1


        return max_num

시간초과.

---

좀더 깔끔한 브루트포스

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        maxsum = nums[0]
        for i in range(len(nums)):
          cursum = 0

          for j in range(i, len(nums)):
            cursum += nums[j]
            maxsum = max(maxsum, cursum)

  return maxsum

 

 

---

카데인 알고리즘

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
      cursum, maxsum = 0, nums[0]

      for i in range(len(nums)):
        cursum = max(nums[i], cursum + nums[i])
        maxsum = max(cursum, maxsum)

      return maxsum

 

---

이전의 누적합이 -가 된다면 필요없다고 판단, 제거하고 연산을 이어나가는 풀이.

카데인 알고리즘에서 불필요한 연산을 더욱 줄였다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        
        maxSum = nums[0]
        curSum = 0

        for n in nums:
            if curSum < 0:
                curSum = 0
            curSum += n
            maxSum = max(maxSub, curSum)
        return maxSub