Make a little progress every day , It's already great , Insist on , Don't be too tired , Refuse to roll in , Start with practice every day , Ten minutes a day , Live happily all your life ！ The epidemic is still repeated , Everyone wear masks ~ Continue to continue , Come on , Today and Brother cheshen Work together to improve your Python Programming and Interview ability Well , brush ladder on high buildings ~
Put on what I took Photo Well ！
Recommend a song every day ： Give you a little red flower —— Zhao Yingjun
The following is my Ladder integral rule ：
At least one question a day ： An integral +10 branch
If you do one more question （ Or one more way to answer ）, Then the points of the day +20 branch （+10+10）
If you do more than three , Start with question 3 +20 branch （ Such as ： If you do three questions, you will score -10+10+20=40; If you do four questions, you will score –10+10+20+20=60）Initial classification 100 branch
If you haven't done the problem for one day , Then deduct points -10 branch （ Saturday 、 Except Sunday ： rest ）
insist ！！！
Give you an array of integers nums , Please find a continuous subarray with the largest sum （ A subarray contains at least one element ）, Return to its maximum and .
Subarray Is a continuous part of the array .
Example 1：
Input ：nums = [-2,1,-3,4,-1,2,1,-5,4]
Output ：6
explain ： Continuous subarray [4,-1,2,1] And the biggest , by 6 .
Example 2：
Input ：nums = [1]
Output ：1
Example 3：
Input ：nums = [5,4,-1,7,8]
Output ：23
analysis ：
Dynamic programming , Determine the state transition function , We just need to sum the maximum suborder of the current previous element to a positive number , Add up ; Otherwise, take the current element as the maximum suborder and .
class Solution: def maxSubArray(self, nums: List[int]) -> int: n = len(nums) dp = [0]*n # dp[i] It means the first one i The maximum suborder sum of elements # The boundary conditions dp[0] = nums[0] # The maximum suborder sum of the first element is itself # Traverse for i in range(1, n): if dp[i-1] > 0: dp[i] = dp[i-1] + nums[i] # If the maximum suborder sum of the previous number is positive , Then add else: dp[i] = nums[i] # If the previous number is negative , Then it is the maximum suborder sum return max(dp)
Let's stop here for today ！
author ： Power button (LeetCode)
link ：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnumcr/
source ： Power button （LeetCode）
Score today ：+10
Total score ：790come on. ！！！
