•
•
문제 설명 : 주어진 배열의 하위 배열 중 가장 합산이 큰 결과를 반환
•
풀이 방법
◦
SubArray 문제의 계산이 필요한 문제 중 가장 중요한 부분은, SubArray를 유지할 수 있는 조건인 것 같다.
◦
이 문제의 경우에도, 지금까지의 SubArray의 합산이 0보다 작다면 굳이 해당 하위 배열은 가져갈 필요가 없다.
▪
이를 total = 0 으로 초기화 시키는 방식으로 버린 후, 다시 처음부터 다시 계산한다.
•
시간복잡도 :
•
성공 코드
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
res = nums[0]
total = 0
for n in nums:
# subarray가 끊기는 시점
if total < 0:
total = 0
total += n
res = max(res, total)
return res
Python
복사