不相交的线&&最大子序和

发布时间:2024年01月22日

我们在两条独立的水平线上按给定的顺序写下?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?,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

示例:

  • 输入: [-2,1,-3,4,-1,2,1,-5,4]
  • 输出: 6
  • 解释:?连续子数组?[4,-1,2,1] 的和最大,为?6。

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

?

?

文章来源:https://blog.csdn.net/Zxy18327720221/article/details/135737463
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。