53. Maximum Subarray

1. 코드

class Solution:
    def maxSubArray(self, nums: List[int]) -> int: 
        
        max_value = nums[0]
        current_sum = nums[0]
        
        for i in range(1, len(nums)) :
            current_sum = max(nums[i], current_sum+nums[i])
            max_value = max(max_value, current_sum)
            
        return max_value

2. 풀이

우선, 문제를 제대로 읽기 전에는 이중 for문을 이용할 생각을 했었다.

If you have figured out the O(n) solution ...

이렇게 나와서 생각해보니 반복문 하나로도 해결할 수 있을 것 같다고 느낌이 들었는데

다만, Kadane's Algorithm은 생각하지 못했다

그래서 우선 이 알고리즘에 대해 먼저 공부해야 하는데, 자세한 부분은 이 블로그에서 공부했다

최대값 max_value 와 누적합계 current_sum 을 갱신해나아가는 방식이며,

그 때의 최대값을 리턴하는 방식이다