300.最長上昇サブシーケンス(動的計画or動的計画+二分検索)
2824 ワード
無秩序な整数配列を指定し、最長上昇サブシーケンスの長さを見つけます.
例:
説明:最長上昇サブシーケンスの組み合わせが複数ある可能性があり、対応する長さだけ出力すればよい. あなたのアルゴリズムの時間的複雑さはO(n 2)であるべきです.
ステップアップ:アルゴリズムの時間的複雑さをO(n log n)に下げることができますか?
【中等】【分析】動的計画:状態+状態遷移方程式.初期化 O ( n 2 ) O(n^2) O(n2)
【解析】ダイナミックプランニング+二分検索 O ( n l o g n ) O(nlogn) O(nlogn); dpに入れる もし
例:
: [10,9,2,5,3,7,101,18]
: 4
: [2,3,7,101]， 4。
説明:
ステップアップ:アルゴリズムの時間的複雑さをO(n log n)に下げることができますか?
【中等】【分析】動的計画:状態+状態遷移方程式.
dp[i]をnum[i]で終わる前面子列{num[0],...,num[i]}の最長上昇子列の長さとする.dp[i]=1dp[i]=max{dp[i],dp[j]+1} for j in range(i) if dp[i]>dp[j] class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums)==0:
return 0
dp=[1 for i in range(len(nums))]
for i in range(1,len(nums)):
for j in range(i):
if nums[i]>nums[j]:
dp[i]=max(dp[i],dp[j]+1)
return max(dp)
【解析】ダイナミックプランニング+二分検索
numsの値をdpの下付き文字で表し、その値が現在位置で最も長い上昇サブストリング長−1(なぜ−1なのか、下付き文字が0から始まるため)をdpの下付き文字で表す.dp[-1] : nums[i]dpの に わる . そうでなければdpで を してdp[j]>=nums[i] and dp[j-1] j nums[i]; これにより における の がO(n)O(n)O(n)からO(l o g n)O(logn)O(logn)に し,dp の が に していることが えられる.
resdp に い、 サブストリング の をとる. e.g. nums=[1,3,6,7,9,4,10,5,6] dp=[1],res=1 dp=[1,3],res=2 dp=[1,3,6],res=3 dp=[1,3,6,7],res=4 dp=[1,3,6,7,9],res=5 dp=[1,3,4,7,9],res=5nums[i]=4の 、4 insertをdpに れ、 でinsertすべき を つける. dp=[1,3,4,7,9,10],res=6 dp=[1,3,4,5,9,10],res=6 dp=[1,3,4,5,6,10],res=6
:#resは、 のiまでの サブ の さであり、dpで に される の の き でもあります.class Solution(object):
def lengthOfLIS(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp=[0 for i in range(len(nums))]
res=0
for i in range(len(nums)):
l,r=0,res
while l>1
if dp[mid]>=nums[i]:
r=mid
else:
l=mid+1
dp[l]=nums[i]
res=max(res,l+1)
return res
:whileに って を して、 みに です!