[LeetCode] Maximum Subarray(python, 최대 서브배열,dp)

합이 최대인 부분 배열을 찾는다 

현재 값 혹은 현재값 + 이전까지의 합이 큰지 비교해서 더 큰 값을 dp배열에 넣고 최대 값을 리턴하면 된다.

O(n)이 걸린다

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        answer=[nums[0]]
        for i in range(1,len(nums)):
            answer.append(nums[i]+(answer[i-1] if answer[i-1]>0 else 0))
                
        return max(answer)
            
            
            

 

* 카데인 알고리즘 (가끔 알고리즘이나 자료구조 공부할 때 항상 등장하는 부분배열 최대값 구하기 알고리즘이다

O(n)에 구할 수 있다

현재의 부분 배열 합과 리턴해줄 최대값을 비교해 더 큰 값으로 계속 갱신해준다

import sys
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans=-sys.maxsize
        temp=0
        for num in nums:
            temp=max(temp+num,num)
            ans=max(ans,temp)
        return ans