리트코드-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.
풀이
주어진 배열 중 합이 가장 큰 서브배열의 합을 구하는 문제다. 이를 풀기 위해서 다음과 같은 생각을 했다.
- 서브 배열의 합만 구하면 되기 때문에, 인덱스 0부터 n까지 누적합을 차례대로 구하는 방식인 DP를 응용하기로 했다.
- 최대값을 구하는 것이므로 이전 인덱스의 누적합이 음수이면 더하지 않기로 했다.
코드
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
answer = nums[0]
for i in range(1, len(nums)):
nums[i] = max(nums[i], nums[i] + nums[i-1])
answer = max(nums[i], answer)
return answer
Author And Source
이 문제에 관하여(리트코드-53. Maximum Subarray), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ddaynew365/53.-Maximum-Subarray저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)