我们在两条独立的水平线上按给定的顺序写下?A?和?B?中的整数。
现在,我们可以绘制一些连接两个数字?A[i]?和?B[j]?的直线,只要?A[i] == B[j],且我们绘制的直线不与任何其他连线(非水平线)相交。
以这种方法绘制线条,并返回我们可以绘制的最大连线数。
class Solution:
? ? def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
? ? ? ? dp=[[0]*(len(nums2)+1) for _ in range(len(nums1)+1)]
? ? ? ? for i in range(1,len(nums1)+1):
? ? ? ? ? ? for ?j in range(1,len(nums2)+1):
? ? ? ? ? ? ? ? if nums1[i-1]==nums2[j-1]:
? ? ? ? ? ? ? ? ? ? dp[i][j]=dp[i-1][j-1]+1
? ? ? ? ? ? ? ? else :
? ? ? ? ? ? ? ? ? ? dp[i][j]=max(dp[i][j-1],dp[i-1][j])
? ? ? ? return dp[-1][-1]
给定一个整数数组 nums?,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
class Solution:
? ? def maxSubArray(self, nums: List[int]) -> int:
? ? ? ? dp=[0]*len(nums)
? ? ? ? dp[0]=nums[0]
? ? ? ? result=dp[0]
? ? ? ? for i in range(1,len(nums)):
? ? ? ? ? ? dp[i]=max(dp[i-1]+nums[i],nums[i])
? ? ? ? ? ? result=max(dp[i],result)
? ? ? ? return resul
?
?