leetcode 53 - Maximum Subarray

 

 

합이 최대가 되는 subarray를 찾고 그 합을 구하는 문제이다.

O(n)으로 풀지 않으면 Times Limit Exceeded가 뜬다. 따라서 Brute force로 풀면 array를 탐색하면서 가능한 모든 subarray를 비교하게 될 것이다.

 

코드는 짧지만 subarray의 합이 최대가 되는 경우를 생각해야 한다. current_sum이라는 값을 두고, max_sum이라는 값을 따로 둔다. current_sum은 이전에 구한 합과 현재의 값을 비교하여 더 큰 값을 저장하는 변수다. max_sum은 첫 번째 값으로 초기화한 뒤 current_sum과 비교해 더 큰 값을 항상 저장한다.

 

current_sum은 현재 index의 값을 포함하는 값 중 최대가 되는 합이고, max_sum은 전체 array에서 최대가 되는 합이라고 생각하면 된다. 매번 index를 바꿀 때마다 이전에 구한 최대값과 현재 index를 포함하는 subarray의 최대값을 비교하는 것이다.

 

 

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        current_sum = nums[0]
        max_sum = nums[0]

        for i in range(1, len(nums)):      
            current_sum = max(current_sum + nums[i], nums[i])
            max_sum = max(current_sum, max_sum)

        return max_sum