수열에서 연속된 구간의 최대 합 구하기

수열에서 연속된 구간의 최대 합 구하기

Largest Sum Contiguous Subarray / Maximum subarray problem

---

유명한 문제로, 주어진 수열에서 최대 합을 구하는 것이 요점이다. 

쉽게 생각하자면 O(n^2)으로 구하면 되지만 (Brute Force), 대부분의 문제 풀이 사이트에서는 O(n)으로 풀기를 권고하고 있다.

제일 무난 한것이 Dynamic Programming으로 푸는 것인데, Kadane’s Algorithm이라고 한다. 

현재 까지의 구간의 최대 합과, 해당 숫자와 Max 값을 비교하고 이 값을 다시 전체 합과 Max 값을 비교하는 것이다.

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        temp_sum = nums[0]
        result = nums[0]
        
        for idx in range(1, len(nums)):
            temp_sum = max(temp_sum + nums[idx], nums[idx])
            result = max(temp_sum, result)
            
        return result

이 밖에도 다양한 풀이 방법이 있는데, 나도 잘 모르기 때문에 위키 피디아에서 살펴 보길 바란다.

최대 합 뿐만 아니라, 어떤 인덱스도 구할 수 있는데, Geeks for Geeks에 잘 나와 있다.

해당 문제를 풀 수 있는 OJ 사이트 주소들은 아래와 같다.

솔직히 O(n)으로 푸는 건 easy 문제 아닌 것 같다..

• https://algospot.com/judge/problem/read/MAXSUM
• https://leetcode.com/problems/maximum-subarray/description/
• https://www.acmicpc.net/problem/10211
• https://www.acmicpc.net/problem/1912