53. Maximum Subarray - python3

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

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

My Answer 1: Time Limit Exceeded (201 / 202 test cases passed.)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        sum1 = min(nums)
        for i in range(0, len(nums)):
            sum2 = 0
            for j in range(i, len(nums)):
                sum2 += nums[j]
                sum1 = max(sum1, sum2)
        return sum1

sum1은 max 값을 찾는데 이용
sum2는 그때그때의 합을 의미

아무래도 내사랑 이중for문 써서 타임리밋 된 듯
O(n)으로 만들어보자...

My Answer 2: Accepted (Runtime: 64 ms / Memory Usage: 15 MB)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        sum1 = min(nums)
        sum2 = 0
        for i in range(0, len(nums)):
            if sum2 < 0:
                sum2 = 0
            sum2 += nums[i]
            sum1 = max(sum1, sum2)
        return sum1

안에 for 문을 지우고 sum2 < 0 이면 sum2 = 0 을 추가

뭔가 일주일 알고리즘 연마를 통해 풀이 능력이 확실히 향상되긴 한듯?!
나의 트라우마.. stock 문제 풀이의 형식을 생각하며 풀었다

Other Answer 1:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSub = nums[0]
        curSum = 0
        
        for n in nums:
            if curSum < 0:
                curSum = 0
            curSum += n
            maxSub = max(maxSub, curSum)
            
        return maxSub

찾아보니 내가 푼거랑 비슷한 답도 있음

재귀로 풀어도 ㄱㅊ을거같지만... 난 여기서 만족