[Leetcode]53. Maximum Subarray

1. 문제 : 

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
 

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.

 

2. 풀이 : 

이 문제는 Dynamic programming을 이용한 풀이다. 이때,

Kadane's Algorithm을 이용한다.

Kadane's Algorithm이란?

Kadane's Algorithm은 주어진 배열에서 연속된 원소들로 이루어진 부분 배열 중 최대 합을 찾는 효율적인 알고리즘이다. 이 알고리즘은 동적 프로그래밍(Dynamic Programming) 기법을 활용하여 O(n) 시간 복잡도로 문제를 해결한다.

 

즉 , 값을 기억해 놓고, 계속해서 값을 경신한다. 이 때문에 in place에서 배열을 조작할 수 있어, 공간복잡도가 O(1)이 나온다.  

 

첫 번째, Kadane's algorithm을 이용한 풀이다. 

current_sum과 global_max를 저장해 두고, 배열을 순회하면서 계속 갱신한다. 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        current_sum = max_sum = nums[0]

        for num in nums[1:]:
            current_sum = max(num, current_sum + num) 
            max_sum = max(current_sum,max_sum)
        return max_sum

current_sum = num과 current_sum + num의 크기를 비교해 더 큰 값을 current_sum으로 둔다. 그렇다면, 어떤 원리일까? 

current_sum이 -2이라고 쳐보자. 이때 num값이 3이다. -2 +3 == -1이다. 3이라는 값을 더할 건데, -2와 같은 작은 값에서 더할 것인가? 아니면 3부터 다시 시작할 것인가? 이러한 논리다. 

max_sum은 순회하면서 나온 당대 max값들을 갱신한다. 

 

두 번째, recursion을 이용한 풀이다. 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def recursive_sum(n):
            nonlocal global_maximum 
            if n == -1:
                return 0
            current_sum = max(recursive_sum(n-1)+nums[n],nums[n])
            global_maximum = max(current_sum,global_maximum)
            return current_sum 
        if not nums:
            return 0
        global_maximum = nums[0]
        recursive_sum(len(nums)-1)
        return global_maximum

첫 번째 , method안에 함수를 새로 작성했다. 그 이유는 n값이 필요했기 때문이다. 

두 번째, base case를 둔다. 

세 번째, n-1일 때 성립한다고 가정한다. 

네 번째, n일 때도 성립한다고 믿는다. 

다섯 번째, base case와 recursive case를 혼합한다. 

여섯 번째, work flow를 적는다.