VB_Python代码对照算法百题(028)

VB代码：（2018年8月温州）17．【加试题】在数组a中按顺序找出一组升序子序列，可以不连续，但要求长度最长。例如：数组a的值分别为2,11,4,13,5,7。升序子序列分别有[2,11]、[2,4]、[2,11,13]、[2,4,13]、[2,4,5]、[2,4,5,7]、[11,13]、[4,13]、[4,5]、[4,5,7]、[5,7]，其中最长升序子序列的数据是2,4,5,7。
算法思路如下：
（1）求以a(i)为结尾元素的最长升序子序列时，找到所有序号j(j=1,2……i-1)，且a(j)<a(i)。如果这样的元素存在，且d(j) >= d(i)（d(i)记录i位置的最长升序子序列长度），那么就增加i位置的最长升序子序列长度，并记录该升序子序列倒数第二个位置。
（2）在d数组中找出最大值，即最长升序子序列长度。
（3）例如，2、11、4、13、5、7，d(1)=1,d(2)=2,d(3)=2,d(4)=3,d(5)=3,d(6)=4，所以最长升序子序列长度为4，是以a(6)为结尾元素。
现设计了如下VB程序，界面如图所示，请回答下列问题：

（1）观察上图，最长升序子序列的数据是          。

（2）请在划线处填入合适的代码。
Const n = 9
Dim a(1 To n) As Integer
Private Sub Form_Load()
‘生成n个[1,10]范围的随机数，存储在a数组，并显示在列表框List1。代码略
End Sub
Private Sub Command1_Click()
Dim d(1 To n) As Integer ‘记录i位置的最长升序子序列长度
Dim pre(1 To n) As Integer ‘记录i结尾的最长升序子序列前一数据的位置
Dim st As String, i As Integer, k As Integer, maxlen As Integer
For i = 1 To n  

    d(i) = 1
Next i
For i = 2 To n  

    For j = 1 To i – 1  

        If a(j) < a(i) And d(j) >= d(i) Then  

            d(i) = 　　　　①
            pre(i) = j  

        End If  

    Next j
Next i
maxlen = 0 : k = 0
For i = 1 To n  

    If 　　　　② Then maxlen = d(i) : k = i
Next i
Do While k <> 0  

    st =str( a(k)) & “,” & st 　

    　　　　③
Loop
Text1．Text = Mid(st, 1, Len(st) – 1)
End Sub

参考答案：

(1) (1分)3,4,6,7,9
(2) ① (1分) d(j)+1或d(i)+1
②(2分) maxlen<d(i)
③(2分) k=pre(k)

Python参考代码：

a=[10,3,4,2,6,7,1,2,9]

d=[1,1,1,1,1,1,1,1,1]

pre=[0,0,0,0,0,0,0,0,0]

st=”

n=len(a)

for i in range(1,n):

    for j in range(i):

        if a[j]<a[i] and d[j]>=d[i]:

            d[i]=d[i]+1

            pre[i]=j

maxlen=0

k=0

for i in range(n):

    if maxlen<d[i]:

        maxlen=d[i]

        k=i

while k!=0:

    st=str(a[k])+’,’+st

    k=pre[k]

print(‘最长(不连续)升序列：’,st)

<a[i] and=”” style=”box-sizing: border-box;color: rgb(74, 74, 74);font-family: Avenir, -apple-system-font, 微软雅黑, sans-serif;font-size: 16px;white-space: pre-line;background-color: rgb(255, 255, 255);”>

Python代码运行结果：