Leetcode 문제
이번에 풀어볼 문제는 리트코드 53번 문제 Maximum Subarray 다.
우선 문제를 살펴보자.
리트코드 53번 문제 Maximum Subarray (링크)
Maximum Subarray - LeetCode
Can you solve this real interview question? Maximum Subarray - Given an integer array nums, find the subarray with the largest sum, and return its sum. Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has t
leetcode.com
Given an integer array nums, find the subarray with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
문제 설명
문제를 간략히 살펴보자.
정수로 이루어진 배열이 주어지는데 이때 그 배열의 subarray 중 그 합이 가장 큰 subarray를 찾아 그 합을 출력하라는 문제다.
문제가 매우 단순명료 하기 때문에 곧바로 문제를 풀어보도록 하자.
문제 접근법 1
이 문제를 푸는 방식에는 여러가지가 있을 수 있는데, 푸는 방식에 따라 time complexity가 크게 달라질 수 있다.
예를 들어 배열 내 위치한 모든 subarray를 찾아 그 subarray들의 합을 구하고 서로 비교한다면
time complexity가 어마무시하게 커질 것이다.
따라서 좀 더 효율적으로 푸는 방식을 생각해 볼 필요가 있다.
가장 쉽게 접근할 수 있는 방법은 Kadane's algorithm으로 알려져있는 방법이다.
이 방식은 첫번째 인덱스에 해당하는 수부터 배열의 숫자들을 하나씩 더하며, 그 중 최대값을 갖는 합을 구하는 것이다.
곧바로 코드를 살펴보는 것이 이해하는데 더 쉽다.
문제 풀이 1
우선 배열을 입력받을 함수를 정의해 준다 (line 1)
그리고 최대 합과 현재의 합을 저장해 줄 변수를 인덱스의 첫번째 값으로 초기화 시켜준다 (line 2-3)
해당 배열의 index=1 부터 마지막까지 for loop를 돌리는데 (line 5)
이때 해당 인덱스에서의 값과, 그 값과 현재까지의 합을 더한 값을 비교해 더 큰 값을 취한다 (line 7)
이 코드의 의미를 해석하면,
해당 인덱스의 값을 취한다는 것은 그 값이 이전까지의 합에 자신을 더한 값보다 크기 때문에 해당 인덱스부터의 subarray를 가지고 계산하면 된다는 뜻이고,
반대로 이전까지의 합과 자신의 합을 취한다는 의미는 이전부터 계산한 subarray에 해당 인덱스 값을 추가하여 새로운 subarray의 합을 구한다는 의미이다.
그리고 그 두개의 값 중 더 큰 값을 지금까지 구한 최대 합의 값과 비교해 더 큰 값을 취한다. (line 10)
이 코드가 필요한 이유는 배열이 굉장히 긴 경우를 생각해보면 쉽다.
예를 들어 배열의 길이가 50개 이고,
처음 10개의 배열이 모두 1로, 그 다음 30개는 0으로, 그리고 마지막 10개는 5로 이루어진 배열을 생각해보자.
이 배열에서 local sum은 두 곳 (처음 10개 그리고 마지막 10개) 존재하는데,
우리는 그 합이 최대가 되는 subarray를 찾아야 하기 때문에 global max sum을 구해야 하기 때문에 line 10이 필요하다.
최대 합을 구해다면 값을 리턴해주면 된다 (line 12)
문제 풀이 코드 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
def maxSubArray(nums):
max_sum = nums[0] # Initialize the maximum sum with the first element
current_sum = nums[0] # Initialize the current sum with the first element
for num in nums[1:]:
# Update the current sum by either adding the current element or starting a new subarray
current_sum = max(num, current_sum + num)
# Update the maximum sum if the current sum is greater
max_sum = max(max_sum, current_sum)
return max_sum
# Test cases
nums1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums1)) # Output: 6
nums2 = [1]
print(maxSubArray(nums2)) # Output: 1
nums3 = [5, 4, -1, 7, 8]
print(maxSubArray(nums3)) # Output: 23
|
cs |
문제 접근법 2
이 문제를 푸는 또 다른 방식은 two pointers를 이용하는 것이다.
이전 문제에서도 몇 번 다루었듯이 left, right pointers를 움직여가며 subarray의 합을 구할 수 있다.
기본적인 아이디어는 right pointer를 첫번째 인덱스부터 하나씩 오른쪽으로 옮겨가며 합을 구한다.
이때 그 합이 음수가 된다면 left pointer를 하나 오른쪽으로 옮겨준다.
우리는 최대 합을 찾고 있는데, right pointer를 옮겨 더했음에도 불구하고 아직 그 합이 음수라면 우리는 그 값을 제외하는 것이 최대 합을 찾는 방향이기 때문이다.
문제 풀이 2
코드를 한 번 살펴보자.
우선 배열을 입력받을 함수를 정의해 준다 (line 1)
그리고 배열의 길이와 left, right pointer를 정의한다 (line 2-4)
최대 합은 우선 첫번째 인덱스 값으로 초기화를 시켜주고 (line 5)
현재 까지의 합은 0으로 초기화를 시켜준다.
앞서 설명했듯 right pointer를 오른쪽으로 (배열 길이까지) 옮겨가며
해당 인덱스 값을 현재까지 합에 더해준다 (line 8-9)
그리고 그 값과 현재까지 구한 최대 합 중 더 큰 값을 취해준다 (line 10)
그 후 right pointers를 하나 오른쪽으로 옮긴다.
이때 중요한 것이 만약 현재까지 합이 음수일 경우인데
음수는 subarray의 합을 최대화 시키는데 반대되는 요소이기 때문에
그 값을 제외시키고 left pointers를 오른쪽으로 한 칸 옮긴다. (line 13-4)
이 과정을 반복하다보면 현재까지의 합이 양수인 상태에서
right pointer를 오른쪽으로 한 칸씩 옮겨가며 그 합이 최대가 되는 값을 찾을 수 있다.
문제 풀이 코드 2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
def maxSubArray(nums):
n = len(nums)
left = 0 # Left pointer
right = 0 # Right pointer
max_sum = nums[0] # Initialize the maximum sum with the first element
current_sum = 0 # Initialize the current sum
while right < n:
current_sum += nums[right]
max_sum = max(max_sum, current_sum)
while current_sum < 0 and left <= right:
current_sum -= nums[left]
left += 1
right += 1
return max_sum
# Test cases
nums1 = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums1)) # Output: 6
nums2 = [1]
print(maxSubArray(nums2)) # Output: 1
nums3 = [5, 4, -1, 7, 8]
print(maxSubArray(nums3)) # Output: 23
|
cs |
관련 문제
리트코드 11번 문제 Container with most water 문제풀이
리트코드 33번 문제 Search in rotated sorted array 문제풀이
리트코드 121번 문제 Best time to buy and sell stock 문제풀이
리트코드 152번 문제 Maximum product subarray 문제풀이
리트코드 153번 문제 Find minimum in rotated sorted array 문제풀이
리트코드 217번 문제 Contains duplicate 문제풀이
리트코드 238번 문제 Product of array except self 문제풀이
