[hero planet July training leetcode problem solving daily] dynamic planning on the 28th

daily

• Today's topic is the largest sub paragraph and , Also known as the largest subarray , classical kadane Algorithm , It is a common algorithm in the field of graphics .
• meanwhile , This is also my entry question , Enjoy the beauty of Algorithm . Start with this question , I find my brain is not enough , With routines, you can kill seconds ！
• This problem was first solved by Brown University Ulf Grenander Professor Yu 1977 in , At first, he wanted to show a simple maximum likelihood estimation model in digital images . Soon after, Carnegie Mellon University Jay Kadane A linear algorithm for this problem is proposed .

subject

One 、 53. Maximum subarray and

link : 53. Maximum subarray and

1. Title Description

2. Thought analysis

• The classic is to find the sum of the largest subsegments , Definition dp[i] For i Is the maximum sum of the ending subparagraphs .
• obviously , If dp[i-1] non-negative , It can be accumulated ,dp[i]=a[i]+dp[i-1];
• otherwise , Give up the previous paragraph , Restart the segment ,dp[i] = a[i].
• Last , We find that state transition is only related to the upper layer , Therefore, space can be optimized , Realization O(1) Complexity .

3. Code implementation

class Solution:


    # def maxSubArray(self, nums: List[int]) -> int:
        # n = len(nums)
        # dp = [0] * n
        # dp[0] = nums[0]
        # for i in range(1,n):
        # if dp[i-1] <= 0:
        # dp[i] = nums[i]
        # else:
        # dp[i] = nums[i] + dp[i-1]
        # return max(dp)


    def maxSubArray(self, nums: List[int]) -> int:
        n  = len(nums)
        dp = nums[0]
        ans = dp
        for a in nums[1:]:            
            dp = a if dp <= 0 else dp + a
            if ans < dp :
                ans = dp
        return ans