[LeetCode 풀이/python] 53. Maximum Subarray (easy)

문제 설명: 정수 배열 nums 가 주어졌을 때, 연속된 부분 배열(적어도 하나의 숫자를 포함하는) 중 가장 큰 합을 만들어내는 것을 찾고 그 합을 리턴하시오.

 

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

 

예시 1)

입력: nums = [-2,1,-3,4,-1,2,1,-5,4]  -->  출력: 6

설명: subarray [4,-1,2,1] 일 때 가장 큰 합 6을 만들 수 있다

 

예시 2)

입력: nums = [1]  -->  출력: 1

 

예시 3)

입력: nums = [0]  -->  출력: 0

 

예시 4)

입력: nums = [-1]  -->  출력: -1

 

예시 5)

입력: nums = [-100000]  -->  출력: -100000

 

제한 조건:

• 1 <= nums.length <= 3 * 10^4
• -10^5 <= nums[i] <= 10^5

------ * ------ * ------ * ------

 

[풀이 1안]

• 접근법
  • 이전에 HackerRank 에서 동일한 문제를 끙끙대며 풀다가 생각보다 아주 간결 & 단순하게 구현 가능해서 기록 겸 복습...
  • 배열 nums 의 값을 차례로 탐색하며 max subarray 값의 후보가 될 current subarray sum (cur_sa) 를 더해 나가되,
  • cur_sa 가 negative 일 경우 오히려 subarray sum 값을 작게 만드므로 버리고 새출발을... -->  cur_sa = n
  • 매 스텝 업데이트 된 cur_sa 가 그때까지의 max_sa 보다 클 경우 이를 새로운 max_sa 값으로 업데이트!

 

• 코드 구현

def maxSubArray(nums: List[int]) -> int:
    max_sa = cur_sa = -10**5
    for n in nums:
        if cur_sa < 0:
            cur_sa = n
        else:
            cur_sa += n
            
        if cur_sa > max_sa:
            max_sa = cur_sa
            
    return max_sa

 

 

• 결과
  • 시간 복잡도 O(n) 으로 무난하게 통과~
  • 참고로 해당 문제에 대한 설명 & 풀이는 Wikipedia 에도 자세하게 설명되어 있음 (en.wikipedia.org/wiki/Maximum_subarray_problem)