Leetcode 53. Maximum Subarray

Daehwi Kim·2021년 7월 5일

LeetCode

목록 보기

22/23

53. Maximum Subarray

Easy

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

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

풀이

1. Dynamic Programming을 이용한 풀이

class Solution:
   def maxSubArray(self, nums: List[int]) -> int:
       for i in range(1, len(nums)):
           # 부분합
           nums[i] = nums[i] + (nums[i - 1] if nums[i - 1] > 0 else 0)
       # 부분합들의 최대값
       return max(nums)

nums  =  [-2,  1,  -3,  4,  -1,  2,  1,  -5,  4]
부분합  =  [-2,  1,  -2,  4,   3,  5,  6,  1,   5]
0번째 인덱스의 값 -2 : -2가 최대값
1번째 인덱스의 값 1 : 이전의 값이 음수이기때문에 해당요소가 최대값 -> 1
2번째 인덱스의 값 -3 : 이전의 부분합 + 해당요소가 최대값 -> -2
3번째 인덱스의 값 4 : 이전의 값이 음수이기때문에 해당요소가 최대값 -> 4
4번째 인덱스의 값 -1 : 이전의 부분합 + 해당요소가 최대값 -> 3
5번째 인덱스의 값 2 : 이전의 부분합 + 해당요소가 최대값 -> 5
6번째 인덱스의 값 1 : 이전의 부분합 + 해당요소가 최대값 -> 6
7번째 인덱스의 값 -5 : 이전의 부분합 + 해당요소가 최대값 -> 1
8번째 인덱스의 값 4 : 이전의 부분합 + 해당요소가 최대값 -> 5

이렇게 이전의 부분합이 음수이면 버리고 음수가 아니면 전의 부분합과 해당요소를 더하여 부분합을 구하고 최종적으로 부분합의 최대값을 구하면 연속적인 배열 합의 최대값을 구할 수 있다.

여기서 중요한 것은 nums 리스트를 반복하면서 하위배열요소의 최대값을 구하여 똑같은 하위배열의 중복계산을 하지않아 시간복잡도 O(n)에 푼 것이다. -> Dynamic Programming

2. 카데인 알고리즘을 이용한 풀이

class Solution:
   def maxSubArray(self, nums: List[int]) -> int:
       best_sum = -sys.maxsize
       cur_sum = 0
       
       for num in nums:
       	   # 부분합
           cur_sum = max(num, num + cur_sum)
           # 부분합의 최대값
           best_sum = max(cur_sum, best_sum)
       
       return best_sum