[LeedCode] 53. Maximum Subarray 파이썬 Easy

문제 해석:

정수 배열이 주어진다. 연속적으로 이어진 부분합중 최대값을 구해라.

문제 해설:

1. Brute Force 로 모든 값을 찾아보는 방법외에, 다이나믹 프로그래밍으로 값을 구할 수 있다.
2. 현재 값과 최대값을 담을 변수를 저장하고
3. 두번째 값부터, 최대값을 찾아나간다.
4. 현재 위치와, 이전 위치 + 현재 위치의 값을 비교해서 최대값을 저장한다.
5. 최대값 변수와 4번에서 비교한 최대값을 비교하여 최대값을 구한다.

예제 : -2, 1, -3, 4, -1, 2, 1, -5, 4 에서, 처음 -2은 저장하고 시작한다.
-2와 1의 합과, 1의 값을 비교했을때 1이 더크니 더하지않고 1을 저장한다.
-3에서 -3과 1과의 합 비교시, 합이 더 크기 때문에 값을 갱신한다. 
4로 넘어가기전에, 최대값은 1이며 현재 값은 -2이다.
4로 넘어왔을때, -1과 4의 합보다 4가 크니까, 현재값은 4로, 최대값도 4로 변경된다.
이 방법이 반복되면, 여태 더했던 값보다 큰값이 나오게 된다면 이전값들은 버리는게 되며, 
모두 수행됬을때 최대 연속부분합을 구할 수 있다. 

53. Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: [4,-1,2,1] has the largest sum = 6.

Example 2:

Input: nums = [1] Output: 1

Example 3:

Input: nums = [5,4,-1,7,8] Output: 23

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

소스코드:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curr = maxV = nums[0]
        for num in nums[1:]:
            curr = max(num, curr + num)
            maxV = max(maxV, curr)
        return maxV