[1스4코2파] # 245. LeetCode 53. Maximum Subarray

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (245일차)
[4코1파] 2023.01.13~ (237일차)
[1스4코1파] 2023.04.12~ (148일차)
[1스4코2파] 2023.05.03 ~ (126일차)

Today :

2023.09.05 [245일차]
53. Maximum Subarray
https://leetcode.com/problems/maximum-subarray/

53. Maximum Subarray

문제 설명

정수 원소를 가지는 array 가 주어졌을 때, 각 배열의 subarray(continuous) 합 중에서 가장 큰 값을 return 함

문제 풀이 방법

브루트 포스(brute force) 방법으로 완전 탐색하면 삐빅 time limit exceeded 임
array에 있는 원소들의 현재까지의 합을 maxsum에 할당하고, 현재의 sum 값이 음수로 떨어지면 최대값아니기 때문에 현재의 값을 다시 0으로 할당하면서 sliding window로 풀어나간다!

내 코드

 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
        
        

증빙

여담

회사다닐때보다 더 바쁜 일상 레전드