leetcode#53 Maximum Subarray

1. 문제

• https://leetcode.com/problems/maximum-subarray/
• 

2. 나의 풀이

2-1. 이중 for문으로 돌았더니 시간초과

• nums의 길이가 10**5인데, 이중포문으로 돌면 10**10으로 파이썬이 해결할 수 있는 50만을 넘겨서 시간초과 발생

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if len(nums) < 2:
            return sum(nums)
        
        if len(nums) == 2:
            return max([nums[0], nums[1], nums[0]+nums[1]])
        
        
        maxSum = max(nums)
        for i in range(0, len(nums)-1):
            for j in range(i, len(nums)):
                # print(i,j,nums[i:j+1])
                current_sum = sum(nums[i:j+1])
                maxSum = current_sum if maxSum < current_sum else maxSum
        
        return maxSum

2-2. Kadane 알고리즘 이용하기

Kadane 알고리즘 이해하기

• maxVal 초기값 정하기: 리스트의 숫자들 중 가장 작은 숫자로 초기화
• sumVal은 0으로 초기화
• 리스트의 숫자를 순차적으로 더하면서 현재까지 가장 큰 sumVal을 갱신한다
  1. sumVal += item[i]
  2. 현재까지의 maxVal 업데이트: 만약 sumVal이 maxVal보다 크다면 maxVal 업데이트 (maxVal: 현재까지 더한 결과중에는 지금 결과가 제일 크다는 느낌)
  3. 더해서 0보다 크거면 계속 더해보자(sumVal): 만약 sumVal이 음수라면 0으로 다시 초기화 (더해서 마이너스는 될빠에 안더한다는 느낌)
     

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        maxVal = min(nums)
        sumVal = 0
        
        for i in range(len(nums)):
            sumVal += nums[i]
            
            if sumVal > maxVal:
                maxVal = sumVal
            if sumVal < 0:
                sumVal = 0
        
        return maxVal

3. 남의 풀이

3-1. Kadane’s approach

카데인(Kadane) 알고리즘
각 수들을 더했을때 가장 큰 수가 나오는 연속된 부분을 찾는 알고리즘을 카데인 알고리즘
1. 요소를 하나씩 더하기
2. 더한 값을 변수에 저장
3. 더한 값이 그 마지막 저장해놓은 변수값보다 크면 변수를 대입

• https://kplog.tistory.com/273

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_so_far = -10000000
        max_ending_here = 0

        for i in range(0, len(nums)):
            max_ending_here = max_ending_here + nums[i]
            if (max_so_far < max_ending_here):
                max_so_far = max_ending_here

            if max_ending_here < 0:
                max_ending_here = 0  
        return max_so_far

• https://siahn95.tistory.com/entry/AlgorithmLeetCodeEasyPython-53-Maximum-Subarray
• https://hecodesit.com/maximum-subarray-leetcode-python-solution/
• https://kplog.tistory.com/273#:~:text=%EA%B0%81%20%EC%88%98%EB%93%A4%EC%9D%84%20%EB%8D%94%ED%96%88%EC%9D%84%EB%95%8C,%EB%8F%84%20%EB%A7%8E%EC%9D%B4%20%EC%B6%9C%EC%A0%9C%EB%90%98%EC%97%88%EB%8B%A4%EA%B3%A0%20%ED%95%9C%EB%8B%A4.