1주차 - 53. Maximum Subarray [코딩 인터뷰 공부]

Leetcode 리트코드

nums array 에서 한개 이상의 숫자를 포함한 연속적인 subarray 중 가장 큰 합을 return 하시오.

 

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

.

.

.

.

.

.

.

ms = [0]*len(nums)
for i,num in enumerate(nums):            
    ms[i] = max(ms[i-1] + num, num)
return max(ms)

시간 복잡도 O(n)

공간 복잡도 O(n)

 

런타임: 1268ms, 7.36%

메모리 사용: 25.7MB, 23.27%

 

 

maxsum_till_i = maxsum= nums[0]
for i, num in enumerate(nums[1:],start=1):
    maxsum_till_i = max(maxsum_till_i+num, num)
    maxsum = max(maxsum,maxsum_till_i,maxsum)
return maxsum

시간 복잡도 O(n)

공간 복잡도 O(1)

 

런타임: 608ms, 88.60%

메모리 사용: 25.5MB, 73.08%