LeetCode53. Maximum Subarray-python(easy) DP 마인드

제목 출처:

   https://leetcode.com/problems/maximum-subarray/discuss/20193/DP-solution-and-some-thoughts

제목 분석:

이 문제의 뜻은 매우 간단하다. 즉, 이 수열의 최대 필드와 출력을 제시하는 것이다.예를 들어 [-3, 2, 1, 3, 4, 3, 1, 2, 1, 5, 4], 최대 자단과 [4, -1, 2, 1]의 답은 6이다.
분명히 이것은 최적화 문제로 통상적으로 DP로 해결할 수 있다.DP는 동적 계획을 의미합니다.동적 기획 프로그램 설계는 가장 최적화된 문제를 풀 수 있는 경로와 방법이지 특수한 알고리즘이 아니다.앞에서 말한 검색이나 수치 계산처럼 표준적인 수학 표현식과 명확한 문제풀이 방법을 가지고 있지 않다.동적 기획 프로그램 디자인은 흔히 가장 최적화된 문제를 대상으로 한다. 각종 문제의 성질이 다르기 때문에 가장 우수한 문제를 확정하는 조건도 서로 다르기 때문에 동적 기획의 디자인 방법은 서로 다른 문제에 대해 각기 특색을 가진 문제 풀이 방법이 있고 만능적인 동적 기획 알고리즘이 존재하지 않아 각종 최적화 문제를 해결할 수 있다.따라서 기본 개념과 방법을 정확하게 이해하는 것 외에 반드시 구체적인 문제를 구체적으로 분석하고 풍부한 상상력으로 모델을 구축하고 창조적인 기교로 해답을 구해야 한다.
동적 기획 알고리즘의 기본 사상은 구해를 기다리는 문제를 서로 연결된 몇 개의 자문제로 분해하고 먼저 자문제를 구해한 다음에 이런 자문제의 해답에서 원문제의 해답을 얻는 것이다.반복적으로 나타나는 하위 문제에 대해서는 처음 만났을 때만 해답을 구하고 답안을 보존하여 나중에 다시 만났을 때 직접 답을 인용하여 다시 해답을 구할 필요가 없게 한다.동적 기획 알고리즘은 문제의 해결 방안을 일련의 결정 결과로 간주한다. 탐욕 알고리즘과 달리 탐욕 알고리즘에서 매번 탐욕 준칙을 채택할 때마다 철회할 수 없는 결정을 내린다.동적 기획 알고리즘에서 모든 최우선 결정 서열에 최우선 결정 서열이 포함되어 있는지, 즉 문제가 최우선 결정 서열의 구조적 성격을 가지고 있는지를 고찰해야 한다.
DP와 관련될 때, 우리가 먼저 알아야 할 것은 하위 문제의 격식 (또는 모든 하위 문제의 상태) 이다. 우리가 귀속 관계를 제기하려고 할 때 하위 문제의 격식이 도움이 될 수 있다.이 문제에서 우리는sum(0,i)를 계산하기 위해 두 가지 선택을 할 수 있다. 하나는 a[i]에 원래 계산한sum(0,i-1)를 추가하거나 추가하지 않는 것이다. 이것은 앞의sum가 정수인지 마이너스인지에 달려 있다.플러스이면 더하기, 그렇지 않으면 더하지 않는다.

해결 코드:

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        sum=0;ma=nums[0]
        for i in range(len(nums)):
            if(sum<0):
                sum=nums[i]
            else:
                sum+=nums[i]
            ma=max(ma,sum)
        return ma