简单题之勾股定理

最大连续子序列

最大非连续子序列

#L只有负数，0，一个正数，直接求max(L),否则构建规划项0，对原列表迭代判断 temp=[i for i in L if i&gt;0] if len(temp)&lt;=1: print(max(L)) else:     L.insert(0, 0)   for i in range(len(L)): if i &gt; 1:             L[i] += max(L[:i-1])  # 列表第三个数字开始 等于加上前个数字前的最大数 print(max(L))

更新下写法

<pre><code>s = max(L)  # 默认取列表中最大值 while len(L):  # 逐步缩短列表 for i in range(2, len(L)):  # 非连续,所以最小步长为2         s1 = [j for j in L[::i] if j &gt; 0]  # 过滤小于0的数 if sum(s1) &gt; s and s1 not in L:  # 确保子序列不连续, 并且把最大值赋值给s             s = sum(s1)       L = L[1:]  # 逐步缩短列表 print(s)</code></pre>

互相学习

<pre><code># L_max用来存放L数组中对应位置前N项中的最大子序列的和 L_max = [0] * len(L) if len(L) &lt;= 2: print(max(L)) else: L_max[0] = L[0] L_max[1] = max(L[0], L[1]) for i in range(2, len(L)): # 对L_max[i]的赋值为，以下三项中最大的一项：L_max[i - 1], L[i] + L_max[i - 2], L[i] L_max[i] = max(L_max[i - 1], L[i] + L_max[i - 2], L[i]) print(L_max[-1])</code></pre>

打印最后一项就是结果

# L[k] 表示前 k 个位置的最大非连续子序列和。L[0]=max(L[0],0) L[1]=max(L[0],L[1]) for i in range(2,len(L)):     L[i]=max(L[i-2]+L[i],L[i-1]) print(L[len(L)-1])

动态规划

L.insert(0, 0) # 列表前面都为负数 选择不加 即为加0 for i in range(len(L)): if i &gt; 1: L[i] += max(L[:i-1]) # 列表第三个数字开始 等于加上前个数字前的最大数 print(max(L)) # 输出列表最大的数

循环叠加

<a href="http://www.gznb.xyz/posts/pythonTip-36-最大非连续子序列/">题解： http://www.gznb.xyz/posts/pythonTip-36-最大非连续子序列/</a>

for i in range(2,len(L)):     L[i]=max(max(L[0:i-1]),0)+L[i] print(max(L))

for i in range(2,len(L)): #获取左侧不相连的最大值，循环执行，确保当前点的数值为其与左侧不相连的序列的最大和     tmp=max(L[0:i-1])     L[i]=max(L[i],L[i]+tmp) print(max(L))

L.insert(0,0)
for i in range(2,len(L)):
    L[i] += max(L[:i-1])
print(max(L))

献丑了

详情请跳转：<a href="https://blog.csdn.net/Herishwater/article/details/94546608">https://blog.csdn.net/Herishwater/article/details/94546608</a>

关于动态规划的讲解分析

if max(L)&lt;0: &nbsp; &nbsp; print max(L) else: &nbsp; &nbsp; L[1]=max(L[0],L[1]) &nbsp; &nbsp; for i in range(2,len(L)): &nbsp; &nbsp; &nbsp; &nbsp; L[i]=max(L[i-2]+L[i],L[i-2],L[i],L[i-1]) &nbsp; &nbsp; print L[-1]

自累加 f(x+2)=max(f(x-1),f(x)+L(x+2),f(x),L(x+2))

dp, ans = [[0, L[0]]], L[0] for i in range(1, len(L)):     x = max(dp[i-1][0], dp[i-1][1])     y = dp[i-1][0] + L[i]     dp.append([x, y])     ans = max(x, y) print(ans)

dp, ans = [[0, L[0]]], L[0] for i in range(1, len(L)):     x = max(dp[i-1][0], dp[i-1][1])     y = dp[i-1][0] + L[i]     dp.append([x, y])     ans = max(x, y) # print(&#x27;x = %d, y = %d&#x27; %(x, y)) e = [i for i in L if i &lt; 0] print(max(L) if len(e) == len(L) else ans)

dp, ans = [[0, L[0]]], L[0]for i in range(1, len(L)): x = max(dp[i-1][0], dp[i-1][1]) y = dp[i-1][0] + L[i] dp.append([x, y]) ans = max(x, y) # print(&#x27;x = %d, y = %d&#x27; %(x, y))e = [i for i in L if i &lt; 0]print(min(L) if len(e) == len(L) else ans)

#求L的非连续子序列 def getMaxSub(i,size): &nbsp; &nbsp; if i&gt;=size: &nbsp; &nbsp; &nbsp; &nbsp; return 0 &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; if L[i]&gt;0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return max(L[i]+getMaxSub(i+2,size),getMaxSub(i+1,size)) &nbsp; &nbsp; &nbsp; &nbsp; else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return getMaxSub(i+1,size) print(getMaxSub(0,len(L))) &nbsp; &nbsp;&nbsp;

递归法求非连续子序列

b=L[:] c=L[:] L.sort(reverse=1) sum=0 for i in range(0,len(L)): &nbsp; &nbsp; for j in range(0,len(b)-1): &nbsp; &nbsp; &nbsp; &nbsp; if b[j]==L[i]: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if j!=len(b)-1 and j!=0: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;b[j-1]=0 &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;b[j+1]=0 if b[len(b)-2]&lt;c[len(b)-1]: &nbsp; &nbsp; b[len(b)-2]=0 &nbsp; &nbsp; b[len(b)-1]=c[len(b)-1] for i in range(0,len(L)): &nbsp; &nbsp; if b[i]==b[i-1]==b[i+1]==0: &nbsp; &nbsp; &nbsp; &nbsp; b[i]=c[i] for i in range(0,len(L)): &nbsp; &nbsp; sum=sum+int(b[i]) print(sum)

用了两个复制列表 IDLE里完全可以 为什么到这边就不行了

mx=[0]*len(L) mx[0]=L[0] mx[1]=L[1] for i in range(2,len(L)): &nbsp; &nbsp; mx[i]=max(max(mx[:i-1])+L[i],L[i]) print max(mx)

动态规划迭代算法

原来是小于0就啥都不选！！1

为什么我的不行，不是一样的么？d = [];for i in range(len(L)): &nbsp; &nbsp; d.append(0); d[0] = L[0]; d[1] = max(L[0],L[1]); if len(L)==1: &nbsp; &nbsp; print d[0]; elif len(L)==2: &nbsp; &nbsp; print d[1]; else: &nbsp; &nbsp; for i in range(2,len(L)):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; d[i] = max(d[i-1],d[i-2]+L[i]); &nbsp; &nbsp; print d[len(L)-1]; &nbsp;

# 通过，不过[-2,-3,-1]的最大非连续应该是[-1]吧 r = [0,0] for i in L: &nbsp;&nbsp;&nbsp; r.append(max(i+r[-2], r[-1])) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp; print r[-1]

<pre style="margin-top: 0px; margin-bottom: 0px; white-space: pre-wrap; word-wrap: break-word; font-family: 'Courier New' !important;">1 L = [0, 0] + L
2 n = len(L)
3 dp = [0] * n
4 for i in xrange(2, n):
5 dp[i] = max(dp[i-2]+L[i], dp[i-1])
6 print dp[n-1]</pre>

第36题：最大非连续子序列

正方形拼接

LTC-男人八题之四：新式取石子游戏

加油站

求中位数